Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning.  It is guaranteed that such a partitioning exists.
 
Example 1:
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]


Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

 

Note:

2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Starter code: class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		biggest = A[0]
		newbiggest = A[0]
		lenL = 1
		total = 1
		for itr in A[1:]:
			total += 1
			if itr < biggest:
				lenL = total
				biggest = newbiggest
			elif itr > newbiggest:
				newbiggest = itr
		return lenL


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		res = 0
		v = A[0]
		max_sofar = v
		for i in range(len(A)):
			max_sofar = max(max_sofar, A[i])
			if A[i] < v:
				v = max_sofar
				res = i
		return res + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		a = [A[0]]
		b = [0 for i in range(len(A))]
		for i in range(1, len(A)):
			a.append(max(a[i - 1], A[i]))
		b[-1] = A[-1]
		for i in range(len(A) - 2, -1, -1):
			b[i] = min(b[i + 1], A[i])
		for i in range(len(A) - 1):
			if a[i] <= b[i + 1]:
				return i + 1
		return -1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		mini = [float('-inf')] * n
		maxi = [float('inf')] * n
		mini[0] = A[0]
		maxi[n - 1] = A[n - 1]
		for i in range(1, n):
			mini[i] = max(mini[i - 1], A[i])
		for i in range(n - 2, -1, -1):
			maxi[i] = min(maxi[i + 1], A[i])
		for i in range(n - 1):
			if mini[i] <= maxi[i + 1]:
				return i + 1
		return 0


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		N = len(A)
		maxleft = [None] * N
		minright = [None] * N
		m = A[0]
		for i in range(N):
			m = max(m, A[i])
			maxleft[i] = m
		m = A[-1]
		for i in range(N - 1, -1, -1):
			m = min(m, A[i])
			minright[i] = m
		for i in range(1, N):
			if maxleft[i - 1] <= minright[i]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		large = [0] * n
		small = [0] * n
		(l, s) = (-sys.maxsize, sys.maxsize)
		for i in range(n):
			l = max(l, A[i])
			s = min(s, A[n - 1 - i])
			large[i] = l
			small[n - 1 - i] = s
		for i in range(n):
			if large[i] <= small[i + 1]:
				return i + 1
		return -1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		left = [A[0]]
		for i in range(1, len(A)):
			left.append(max(left[-1], A[i]))
		right = [A[-1]]
		for i in range(len(A) - 2, -1, -1):
			right.append(min(right[-1], A[i]))
		for i in range(1, len(A)):
			if left[i - 1] <= right[-i - 1]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		run_max = [float('-inf')]
		run_min = [float('inf')]
		p = 1
		while p < len(A):
			run_max.append(max(run_max[-1], A[p - 1]))
			p += 1
		p = len(A) - 2
		while p > -1:
			run_min.append(min(run_min[-1], A[p + 1]))
			p -= 1
		run_min = run_min[::-1]
		res = -1
		p = 0
		done = False
		while p < len(A) - 1 and (not done):
			if A[p] <= run_min[p] and run_max[p] <= run_min[p]:
				res = p + 1
				done = True
			p += 1
		return res


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		left_max = []
		right_min = []
		for i in range(len(A)):
			if i == 0:
				left_max.append(A[i])
			else:
				left_max.append(max(A[i], left_max[-1]))
		for i in range(len(A) - 1, -1, -1):
			if i == len(A) - 1:
				right_min.append(A[i])
			else:
				right_min.append(min(A[i], right_min[-1]))
		right_min.reverse()
		for i in range(len(A) - 1):
			lm = left_max[i]
			rm = right_min[i + 1]
			if lm <= rm:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		(max_left, min_right) = ([None] * n, [None] * n)
		max_left[0] = A[0]
		for i in range(1, n):
			max_left[i] = max(max_left[i - 1], A[i])
		min_right[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			min_right[i] = min(min_right[i + 1], A[i])
		for i in range(1, n):
			if max_left[i - 1] <= min_right[i]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		(l, r) = (0, len(A) - 1)
		leftMax = A[l]
		rightMin = A[r]
		minHash = {}
		while l < r:
			leftMax = max(leftMax, A[l])
			rightMin = min(rightMin, A[r])
			if rightMin >= leftMax:
				r -= 1
			else:
				l += 1
		for i in range(r, len(A)):
			if A[i] not in minHash:
				minHash[A[i]] = []
			minHash[A[i]].append(i)
		minHash = sorted(list(minHash.items()), key=lambda x: x[0])
		(i, res) = (0, 1)
		while i < len(minHash) and minHash[i][0] < leftMax:
			positions = minHash[i][1]
			res = max(positions[-1] + 1, res)
			i += 1
		return res


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		mx = [-1] * len(A)
		mn = [-1] * len(A)
		for i in range(len(A)):
			if i == 0:
				mx[i] = A[i]
			else:
				mx[i] = max(A[i], mx[i - 1])
		for j in range(len(A) - 1, -1, -1):
			if j == len(A) - 1:
				mn[j] = A[j]
			else:
				mn[j] = min(A[j], mn[j + 1])
		for i in range(len(A) - 1):
			if mx[i] <= mn[i + 1]:
				return i + 1
		return len(A) - 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		memo = [[0 for _ in range(n)] for _ in range(2)]
		(left, right) = (0, (1 << 31) - 1)
		(i, j) = (0, n - 1)
		while i < n and j >= 0:
			right = min(right, A[j])
			left = max(left, A[i])
			memo[0][i] = left
			memo[1][j] = right
			i += 1
			j -= 1
		(i, j) = (0, 1)
		while j < n and memo[0][i] > memo[1][j]:
			(i, j) = (i + 1, j + 1)
		return j


from collections import Counter

class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		c = Counter(A)
		d = Counter()
		keys = sorted(c.keys())
		d[keys[0]] = 0
		for i in range(1, len(keys)):
			d[keys[i]] = c[keys[i - 1]] + d[keys[i - 1]]
		(lesscount, mx) = (0, -float('inf'))
		equal = 0
		for i in range(len(A)):
			if A[i] < mx:
				lesscount += 1
			elif A[i] == mx:
				equal += 1
			else:
				mx = A[i]
				lesscount += equal
				equal = 1
			if lesscount == d[mx]:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		N = len(A)
		maxLeft = dict()
		minRight = dict()
		if N == 2 and A[0] <= A[1]:
			return 1
		maxLeft[0] = A[0]
		for i in range(1, N - 1):
			maxLeft[i] = max(maxLeft[i - 1], A[i])
		minRight[N - 1] = A[-1]
		for i in range(N - 2, 0, -1):
			minRight[i] = min(minRight[i + 1], A[i])
		print({'maxLeft': maxLeft})
		print({'minRight': minRight})
		for i in range(N - 1):
			if maxLeft[i] <= minRight[i + 1]:
				return i + 1
		return -1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		length = len(A)
		leftMax = A[0]
		currMax = leftMax
		ret = 0
		for i in range(1, length):
			currMax = max(A[i], currMax)
			if leftMax > A[i]:
				leftMax = currMax
				ret = i
		return ret + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		maxval = A[0]
		v = A[0]
		disjoint = 0
		for i in range(len(A)):
			maxval = max(maxval, A[i])
			if A[i] < v:
				disjoint = i
				v = maxval
		return disjoint + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		split_index = 0
		local_max = A[0]
		max_num = local_max
		for i in range(len(A)):
			if A[i] < local_max:
				split_index = i
				local_max = max_num
			else:
				max_num = max(max_num, A[i])
		return split_index + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		minA = [A[0]]
		for i in A[1:]:
			minA.append(max(i, minA[-1]))
		minB = [A[-1]]
		for i in A[:-1][::-1]:
			minB.append(min(minB[-1], i))
		minB = minB[::-1]
		for i in range(1, len(A)):
			if minA[i - 1] <= minB[i]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		max_left = float('-inf')
		min_right = A[-1]
		left = []
		right = [A[-1]]
		for i in range(len(A)):
			max_left = max(max_left, A[i])
			left.append(max_left)
		for i in range(len(A) - 2, -1, -1):
			min_right = min(min_right, A[i + 1])
			right.append(min_right)
		right.reverse()
		for i in range(len(left)):
			if left[i] <= right[i]:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		left = [0] * len(A)
		for i in range(len(A)):
			if i == 0:
				left[i] = A[i]
			elif A[i] > left[i - 1]:
				left[i] = A[i]
			else:
				left[i] = left[i - 1]
		A_reversed = A[::-1]
		right = [0] * len(A)
		for i in range(len(A)):
			if i == 0:
				right[i] = A_reversed[i]
			elif A_reversed[i] < right[i - 1]:
				right[i] = A_reversed[i]
			else:
				right[i] = right[i - 1]
		right = right[::-1]
		print(left, right)
		for i in range(len(left) - 1):
			if left[i] <= right[i + 1]:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		d = [0] * n
		d[n - 1] = A[n - 1]
		for i in range(len(A) - 2, -1, -1):
			d[i] = min(A[i], d[i + 1])
		mx = A[0]
		for i in range(1, n):
			if mx <= d[i]:
				return i
			else:
				mx = max(mx, A[i])


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		least = [float('inf')] * len(A)
		for i in range(len(A) - 1, -1, -1):
			if i == len(A) - 1:
				least[i] = A[i]
			else:
				least[i] = min(least[i + 1], A[i])
		greatest = A[0]
		for i in range(1, len(A)):
			if greatest <= least[i]:
				break
			greatest = max(greatest, A[i])
		return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		l = [0] * len(A)
		r = [0] * len(A)
		for i in range(len(l)):
			l[i] = max(A[i], l[i - 1])
		r[-1] = A[-1]
		for i in range(len(r) - 2, -1, -1):
			r[i] = min(A[i], r[i + 1])
		print(l)
		print(r)
		for i in range(len(l)):
			if l[i] <= r[i + 1]:
				return i + 1
		return len(l)


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		ans = 1
		all_max = A[0]
		curr_max = 0
		for i in range(len(A)):
			curr_max = max(curr_max, A[i])
			if all_max > A[i]:
				all_max = curr_max
				ans = i + 1
		return ans


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		ml = 0
		mx = -1000000000.0
		mxsofar = 1000000000.0
		for (i, a) in enumerate(A):
			mx = max(a, mx)
			if a < mxsofar:
				ml = i + 1
				mxsofar = mx
		return ml


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		right = 1
		maxLeft = A[0]
		sortedRight = sorted(range(right, len(A)), key=lambda k: A[k])
		while A[sortedRight[0]] < maxLeft:
			right = sortedRight[0] + 1
			maxLeft = max(A[:right])
			sortedRight = sorted(range(right, len(A)), key=lambda k: A[k])
		return right


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		m = n - 1
		left_max = [0] * m
		left_max[0] = A[0]
		right_min = [0] * m
		right_min[-1] = A[-1]
		for i in range(1, n - 1):
			left_max[i] = max(left_max[i - 1], A[i])
		for i in reversed(range(1, m)):
			right_min[i - 1] = min(right_min[i], A[i])
		for i in range(m):
			if left_max[i] <= right_min[i]:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		bound = r = 0
		gmax = lmax = A[0]
		while r < len(A):
			if A[r] >= gmax:
				lmax = max(lmax, A[r])
				r += 1
			else:
				bound = r
				gmax = max(gmax, lmax)
				r += 1
		return bound + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		h = {}
		right = float('inf')
		for j in range(len(A) - 1, -1, -1):
			right = min(right, A[j])
			h[j] = right
		left = float('-inf')
		for i in range(len(A) - 1):
			left = max(left, A[i])
			if left <= h[i + 1]:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		cnt = collections.Counter(A)
		cur = 0
		minn = min(cnt.keys())
		for i in range(len(A)):
			cur = max(cur, A[i])
			cnt[A[i]] -= 1
			if cnt[A[i]] == 0:
				del cnt[A[i]]
				if minn == A[i]:
					minn = min(cnt.keys())
			if minn >= cur:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		l = [A[0]]
		r = [A[-1]]
		for (i, v) in enumerate(A):
			if i == 0:
				continue
			l.append(max(l[i - 1], A[i]))
			r.append(min(r[i - 1], A[len(A) - i - 1]))
		r.reverse()
		for i in range(1, len(l)):
			if l[i - 1] <= r[i]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		partidx = 0
		left_max = A[0]
		seen_max = A[0]
		for i in range(1, n):
			seen_max = max(seen_max, A[i])
			if A[i] < left_max:
				partidx = i
				left_max = seen_max
		return partidx + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		i = 1
		l_max = A[i - 1]
		r_min = min(A[i:])
		while l_max > r_min:
			i += 1
			l_max = max(l_max, A[i - 1])
			if A[i - 1] == r_min:
				r_min = min(A[i:])
		return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		n = len(A)
		ma = [0] * n
		mi = [0] * n
		mi[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			mi[i] = min(A[i + 1], mi[i + 1])
		ma[0] = A[0]
		for i in range(1, n):
			ma[i] = max(A[i], ma[i - 1])
		for i in range(n - 1):
			if mi[i] >= ma[i]:
				return i + 1
		return n


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		max_left = list()
		min_right = list()
		for i in range(len(A)):
			left = A[i]
			if i == 0:
				max_left.append(left)
			elif max_left[i - 1] > left:
				max_left.append(max_left[i - 1])
			else:
				max_left.append(left)
			right = A[len(A) - 1 - i]
			if i == 0:
				min_right.append(right)
			elif min_right[i - 1] < right:
				min_right.append(min_right[i - 1])
			else:
				min_right.append(right)
		for i in range(len(A)):
			if max_left[i] <= min_right[len(A) - i - 2]:
				return i + 1
		return 0


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		p = [None] * len(A)
		q = [None] * len(A)
		for (i, v) in enumerate(A):
			if i == 0:
				p[0] = v
			else:
				p[i] = max(p[i - 1], v)
		for (i, v) in enumerate(reversed(A)):
			if i == 0:
				q[len(A) - 1] = v
			else:
				q[len(A) - 1 - i] = min(q[len(A) - i], v)
		for i in range(len(A) - 1):
			if p[i] <= q[i + 1]:
				return i + 1
		return len(A)


from sortedcontainers import SortedList

class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		(left, right) = (SortedList(), SortedList(A))
		for i in range(len(A) - 1):
			left.add(A[i])
			right.discard(A[i])
			if left[-1] <= right[0]:
				break
		return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		i = 1
		l_max = A[i - 1]
		d = Counter(A[i:])
		a_dict = OrderedDict(sorted(d.items()))
		r_min = next(iter(a_dict.items()))[0]
		while l_max > r_min:
			i += 1
			l_max = max(l_max, A[i - 1])
			if a_dict[A[i - 1]] > 1:
				a_dict[A[i - 1]] -= 1
			else:
				del a_dict[A[i - 1]]
				r_min = next(iter(a_dict.items()))[0]
		return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		min_right = min(A)
		max_left = 0
		min_from_right = []
		current_min_right = A[-1]
		for i in range(len(A) - 1, -1, -1):
			current_min_right = min(A[i], current_min_right)
			min_from_right.insert(0, current_min_right)
		for i in range(len(A)):
			current = A[i]
			max_left = max(max_left, current)
			min_right = min_from_right[i + 1] if i < len(A) else 0
			if max_left <= min_right:
				return i + 1


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		maxlefts = []
		minrights = []
		m = A[0]
		for n in A:
			m = max(m, n)
			maxlefts.append(m)
		m = A[len(A) - 1]
		for n in A[::-1]:
			m = min(m, n)
			minrights.insert(0, m)
		for i in range(1, len(A)):
			if maxlefts[i - 1] <= minrights[i]:
				return i


class Solution:

	def partitionDisjoint(self, A: List[int]) -> int:
		left_maxes = A[:]
		right_mins = A[:]
		for i in range(1, len(left_maxes)):
			if left_maxes[i] < left_maxes[i - 1]:
				left_maxes[i] = left_maxes[i - 1]
		for i in range(len(right_mins) - 2, -1, -1):
			if right_mins[i] > right_mins[i + 1]:
				right_mins[i] = right_mins[i + 1]
		for i in range(1, len(A)):
			if left_maxes[i - 1] <= right_mins[i]:
				return i