N Students of different heights are attending an assembly. The heights of the students are represented by an array H[]. The problem is that if a student has less or equal height than the student standing in front of him, then he/she cannot see the assembly. Find the minimum number of students to be removed such that all the remaining students can see the assembly.
 
Example 1:
Input:
N = 6
H[] = {9, 1, 2, 3, 1, 5}
Output:
2
Explanation:
We can remove the students at 0 and 4th index.
which will leave the students with heights
1,2,3, and 5.
Example 2:
Input:
N = 3
H[] = {1, 2, 3} 
Output :
0
Explanation:
All of the students are able to see the
assembly without removing anyone.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function removeStudents() which takes an integer N and an array H[ ] of size N as input parameters and returns the minimum number of students required to be removed to enable all the remaining students to see the assembly.
Expected Time Complexity: O(N logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ H[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def removeStudents(self, H, N):

        # code here

Solutions:
class Solution:

	def removeStudents(self, H, N):
		ans = [H[0]]
		for i in range(1, N):
			if H[i] > ans[-1]:
				ans.append(H[i])
			else:
				l = 0
				r = len(ans) - 1
				while l < r:
					mid = (l + r) // 2
					if ans[mid] < H[i]:
						l = mid + 1
					else:
						r = mid
				ans[l] = H[i]
		return N - len(ans)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		dp = [0] * N
		length = 0
		for i in range(N):
			idx = bisect_left(dp, H[i], 0, length)
			dp[idx] = H[i]
			if idx == length:
				length += 1
		return N - length


class Solution:

	def longestSubseq(self, H, N):
		dp = [0] * N
		size = 0
		for x in H:
			(i, j) = (0, size)
			while i != j:
				m = (i + j) // 2
				if dp[m] < x:
					i = m + 1
				else:
					j = m
			dp[i] = x
			size = max(i + 1, size)
		return size

	def removeStudents(self, H, N):
		s1 = self.longestSubseq(H, N)
		ans = N - s1
		return ans


class Solution:

	def lengthOfLIS(self, nums):
		tails = [0] * len(nums)
		size = 0
		for x in nums:
			(i, j) = (0, size)
			while i != j:
				m = (i + j) // 2
				if tails[m] < x:
					i = m + 1
				else:
					j = m
			tails[i] = x
			size = max(i + 1, size)
		return size

	def removeStudents(self, H, N):
		ans = N - self.lengthOfLIS(H)
		return ans


class Solution:

	def removeStudents(self, arr, N):
		temp = []
		import bisect
		temp.append(arr[0])
		for i in range(1, len(arr)):
			if temp[-1] < arr[i]:
				temp.append(arr[i])
			else:
				j = bisect.bisect_left(temp, arr[i])
				temp[j] = arr[i]
		return len(arr) - len(temp)


import bisect

class Solution:

	def removeStudents(self, arr, n):
		stack = list()
		stack.append(arr[0])
		for i in range(1, n):
			if stack[-1] < arr[i]:
				stack.append(arr[i])
			else:
				left = bisect.bisect_left(stack, arr[i])
				stack[left] = arr[i]
		return n - len(stack)


def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len

class Solution:

	def removeStudents(self, H, N):
		l = LongestIncreasingSubsequenceLength(H, N)
		return N - l


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		if N == 1:
			return 0
		arr = [H[0]]
		for i in range(1, N):
			if arr[-1] < H[i]:
				arr.append(H[i])
			elif arr[0] > H[i]:
				arr[0] = H[i]
			else:
				mid = bisect_left(arr, H[i])
				arr[mid] = H[i]
		return N - len(arr)


from bisect import *

class Solution:

	def removeStudents(self, H, N):

		def f(H, N):
			temp = []
			for i in range(N):
				pos = bisect_left(temp, H[i])
				if pos == len(temp):
					temp.append(H[i])
				else:
					temp[pos] = H[i]
			return len(temp)
		return N - f(H, N)


class Solution:

	def longestSubseq(self, H, N):
		dp = [0] * N
		size = 0
		for x in H:
			l = 0
			r = size
			while l != r:
				m = (l + r) // 2
				if dp[m] < x:
					l = m + 1
				else:
					r = m
			dp[l] = x
			size = max(l + 1, size)
		return size

	def removeStudents(self, H, N):
		l = self.longestSubseq(H, N)
		return N - l


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		ans = [H[0]]
		for i in range(1, N):
			if H[i] > ans[-1]:
				ans.append(H[i])
			else:
				ans[bisect_left(ans, H[i])] = H[i]
		return N - len(ans)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		dp = []
		length = 0
		for i in range(N):
			idx = bisect_left(dp, H[i])
			if idx == len(dp):
				dp.append(H[i])
			else:
				dp[idx] = H[i]
		return N - len(dp)


class Solution:

	def removeStudents(self, H, n):
		stack = [H[0]]

		def binary(stack, cur_ele):
			lo = 0
			hi = len(stack) - 1
			while lo <= hi:
				mid = (lo + hi) // 2
				if stack[mid] < cur_ele:
					lo = mid + 1
				else:
					hi = mid - 1
			return lo
		for i in range(1, n):
			cur_ele = H[i]
			if stack[-1] < cur_ele:
				stack.append(cur_ele)
				continue
			stack[binary(stack, cur_ele)] = cur_ele
		return n - len(stack)


import bisect

class Solution:

	def removeStudents(self, H, N):
		length = list()
		for i in range(N):
			if len(length) == 0:
				length.append(H[i])
			else:
				insert_position = bisect.bisect_left(length, H[i])
				if insert_position == len(length):
					length.append(H[i])
				else:
					length[insert_position] = H[i]
		return N - len(length)


class Solution:

	def removeStudentsDP(self, hts, n):
		dp = [1 for _ in range(n)]
		for ind in range(n):
			for j in range(ind):
				if hts[j] < hts[ind]:
					dp[ind] = max(dp[ind], dp[j] + 1)
		return n - max(dp)

	def removeStudents(self, hts, n):
		from bisect import bisect_left
		ans = [hts[0]]
		for i in range(1, n):
			if ans[-1] < hts[i]:
				ans.append(hts[i])
			else:
				ind = bisect_left(ans, hts[i])
				ans[ind] = hts[i]
		return n - len(ans)


from bisect import bisect_right as upper
import sys

class Solution:

	def removeStudents(self, arr, N):
		dp = [sys.maxsize for i in range(0, N + 1)]
		dp[0] = -sys.maxsize
		for i in range(0, N):
			idx = upper(dp, arr[i])
			if dp[idx - 1] < arr[i] and dp[idx] > arr[i]:
				dp[idx] = arr[i]
		maxlis = 0
		for i in range(N, -1, -1):
			if dp[i] != sys.maxsize:
				maxlis = i
				break
		return N - maxlis


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		ans = []
		for st in H:
			pi = bisect_left(ans, st)
			if pi >= len(ans):
				ans.append(st)
			else:
				ans[pi] = st
		return N - len(ans)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		A = []
		for i in H:
			j = bisect_left(A, i)
			if j == len(A):
				A.append(i)
			else:
				A[j] = i
		return N - len(A)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		result = []
		for el in H:
			idx = bisect_left(result, el)
			if idx >= len(result):
				result.append(el)
			else:
				result[idx] = el
		return N - len(result)


import bisect

class Solution:

	def removeStudents(self, H, N):
		vals = []
		for x in H:
			idx = bisect.bisect_left(vals, x)
			if idx >= len(vals):
				vals.append(x)
			vals[idx] = x
		return N - len(vals)


class Solution:

	def removeStudents(self, H, N):

		def binary_search(A, l, r, key):
			while r - l > 1:
				m = l + (r - l) // 2
				if A[m] >= key:
					r = m
				else:
					l = m
			return r
		LIS = [0 for i in range(N + 1)]
		max_len = 0
		LIS[0] = H[0]
		max_len = 1
		for i in range(1, N):
			if H[i] < LIS[0]:
				LIS[0] = H[i]
			elif H[i] > LIS[max_len - 1]:
				LIS[max_len] = H[i]
				max_len += 1
			else:
				LIS[binary_search(LIS, -1, max_len - 1, H[i])] = H[i]
		return N - max_len


import bisect as bs

class Solution:

	def removeStudents(self, H, N):
		temp = [H[0]]
		maxi = 1
		for i in range(N):
			if temp[-1] < H[i]:
				temp.append(H[i])
				maxi += 1
			else:
				ind = bs.bisect_left(temp, H[i])
				temp[ind] = H[i]
		return N - maxi


class Solution:

	def removeStudents(self, H, N):

		def ceil(tail, left, right, x):
			while right > left:
				mid = left + (right - left) // 2
				if tail[mid] >= x:
					right = mid
				else:
					left = mid + 1
			return right

		def MinDeletion(arr, n):
			tail = [0] * n
			tail[0] = arr[0]
			length = 1
			for i in range(1, n):
				if arr[i] > tail[length - 1]:
					tail[length] = arr[i]
					length += 1
				else:
					c = ceil(tail, 0, length - 1, arr[i])
					tail[c] = arr[i]
			return n - length
		return MinDeletion(H, N)


class Solution:

	def longIncSub(self, h, n):
		dp = [0] * n
		size = 0
		for i in h:
			(x, y) = (0, size)
			while x != y:
				m = (x + y) // 2
				if dp[m] < i:
					x = m + 1
				else:
					y = m
			dp[x] = i
			size = max(x + 1, size)
		return size

	def removeStudents(self, h, N):
		s = self.longIncSub(h, N)
		ans = N - s
		return ans


from bisect import bisect_left

class Solution:

	def lengthOfLIS(self, nums):
		arr = []
		for num in nums:
			insertion_pos = bisect_left(arr, num)
			if insertion_pos == len(arr):
				arr.append(num)
			else:
				arr[insertion_pos] = num
		return len(arr)

	def removeStudents(self, h, n):
		return n - self.lengthOfLIS(h)


class Solution:

	def midIndex(self, left, right, dp, key):
		while right - left > 1:
			mid = left + (right - left) // 2
			if dp[mid] >= key:
				right = mid
			else:
				left = mid
		return right

	def removeStudents(self, H, N):
		ans = []
		ans.append(H[0])
		for i in range(1, N):
			if H[i] < ans[0]:
				ans[0] = H[i]
			elif H[i] > ans[-1]:
				ans.append(H[i])
			else:
				ans[self.midIndex(-1, len(ans) - 1, ans, H[i])] = H[i]
		return N - len(ans)


class Solution:

	def bsearch(self, dp, n, ele):
		l = 0
		h = n
		while l != h:
			mid = (l + h) // 2
			if dp[mid] < ele:
				l = mid + 1
			else:
				h = mid
		return l

	def removeStudents(self, H, N):
		dp = [0] * N
		llen = 0
		for i in range(N):
			ind = self.bsearch(dp, llen, H[i])
			dp[ind] = H[i]
			llen = max(llen, ind + 1)
		return N - llen


def solveTabulation(arr, n, dp):
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -2, -1):
			take = 0
			if j == -1 or arr[i] > arr[j]:
				take = 1 + dp[i + 1][i + 1]
			nottake = dp[i + 1][j + 1]
			dp[i][j + 1] = max(take, nottake)

def binary_search(arr, n, ele):
	i = 0
	j = n - 1
	while i <= j:
		mid = (i + j) // 2
		if ele == arr[mid]:
			return mid
		elif ele > arr[mid]:
			i = mid + 1
		elif ele < arr[mid]:
			j = mid - 1
	return i
from bisect import bisect_left

def optimalSolution(arr, n):
	if n == 0:
		return 0
	temp = [arr[0]]
	for i in range(1, n):
		if arr[i] > temp[-1]:
			temp.append(arr[i])
		else:
			lower_bound = bisect_left(temp, arr[i])
			temp[lower_bound] = arr[i]
	return len(temp)

class Solution:

	def removeStudents(self, arr, N):
		n = len(arr)
		res = optimalSolution(arr, n)
		return n - res


import bisect

class Solution:

	def removeStudents(self, H, N):
		dp = [0] * N
		dp[0] = H[0]
		length = 1
		for i in range(1, N):
			if H[i] < dp[0]:
				dp[0] = H[i]
			elif H[i] > dp[length - 1]:
				dp[length] = H[i]
				length += 1
			else:
				index = bisect.bisect_left(dp[:length], H[i])
				dp[index] = H[i]
		return N - length


class Solution:

	def removeStudents(self, H, N):
		dp = [0] * N
		size = 0
		for h in H:
			(i, j) = (0, size)
			while i != j:
				m = (i + j) // 2
				if dp[m] < h:
					i = m + 1
				else:
					j = m
			dp[i] = h
			size = max(i + 1, size)
		return N - size


class Solution:

	def removeStudents(self, H, N):
		long = 0
		v = [0] * N
		for a in H:
			(i, j) = (0, long)
			found = False
			while i != j:
				m = (i + j) // 2
				if v[m] < a:
					i = m + 1
				else:
					j = m
			v[i] = a
			long = max(i + 1, long)
		return N - long


import math

class Solution:

	def removeStudents(self, H, N):

		def binarysearch(ele, arr):
			l = 0
			h = len(arr) - 1
			while l <= h:
				mid = (l + h) // 2
				if arr[mid] >= ele:
					h = mid - 1
				else:
					l = mid + 1
			return l
		dp = []
		for stu in H:
			idx = binarysearch(stu, dp)
			if idx == len(dp):
				dp.append(stu)
			else:
				dp[idx] = stu
		return N - len(dp)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		dp = []
		for i in H:
			cur = bisect_left(dp, i)
			if cur == len(dp):
				dp.append(i)
			else:
				dp[cur] = i
		return N - len(dp)


def lower_bound(res, a):
	(low, high) = (0, len(res) - 1)
	ans = 0
	while low <= high:
		mid = (high + low) // 2
		if res[mid] > a:
			high = mid - 1
		elif res[mid] < a:
			low = mid + 1
		else:
			return mid
	return low

def solve(arr, N):
	if N == 0:
		return 0
	res = []
	res.append(arr[0])
	for i in range(1, N):
		index = lower_bound(res, arr[i])
		if index == len(res):
			res.append(arr[i])
		else:
			res[index] = arr[i]
	return len(res)

class Solution:

	def removeStudents(self, H, N):
		return N - solve(H, N)


from bisect import bisect_right

class Solution:

	def removeStudents(self, H, N):
		dp = [0] * N
		size = 0
		for x in H:
			(i, j) = (0, size)
			while i != j:
				m = (i + j) // 2
				if dp[m] < x:
					i = m + 1
				else:
					j = m
			dp[i] = x
			size = max(i + 1, size)
		return N - size


class Solution:

	def binary_search(self, dp, start, end, target):
		while start < end:
			mid = (start + end) // 2
			if dp[mid] == target:
				return mid
			elif dp[mid] < target:
				start = mid + 1
			else:
				end = mid
		return start

	def removeStudents(self, H, N):
		dp = [0] * N
		dp[0] = H[0]
		length = 1
		for i in range(1, N):
			if H[i] > dp[length - 1]:
				dp[length] = H[i]
				length += 1
			elif H[i] <= dp[0]:
				dp[0] = H[i]
			else:
				loc = self.binary_search(dp, 0, length - 1, H[i])
				dp[loc] = H[i]
		return N - length


class Solution:

	def removeStudents(self, nums, N):

		def binary(temp, l, r, target):
			while r >= l:
				mid = (l + r) // 2
				if temp[mid] == target:
					return mid
				elif temp[mid] > target:
					r = mid - 1
				else:
					l = mid + 1
			return l
		temp = [nums[0]]
		for i in range(1, len(nums)):
			if nums[i] > temp[-1]:
				temp.append(nums[i])
			else:
				indx = binary(temp, 0, len(temp) - 1, nums[i])
				temp[indx] = nums[i]
		return N - len(temp)


import bisect

class Solution:

	def removeStudents(self, H, N):

		def solve(arr):
			temp = [arr[0]]
			for i in range(1, len(arr)):
				if arr[i] > temp[-1]:
					temp.append(arr[i])
				else:
					idx = bisect.bisect_left(temp, arr[i])
					temp[idx] = arr[i]
			return len(temp)
		return len(H) - solve(H)


from bisect import bisect_left

class Solution:

	def removeStudents(self, H, N):
		a = []
		for i in H:
			b = bisect_left(a, i)
			if b >= len(a):
				a.append(i)
			else:
				a[b] = i
		return N - len(a)


from bisect import bisect_left as nik

class Solution:

	def removeStudents(self, H, N):
		asc_arr = [H[0]]
		for i in range(1, N):
			if H[i] > asc_arr[-1]:
				asc_arr.append(H[i])
			else:
				asc_arr[nik(asc_arr, H[i])] = H[i]
		return N - len(asc_arr)