915. Partition Array into Disjoint Intervals | 1501
When you play maimai at Round1 at 11:00pm and the other one playing with you is a youtube employee that tells you better ways to conquer leetcode.
Will start with rating 1500+ and see if it’s an appropriate level for me.
My initial solution is passing, but it’s using O(nlogn) (i sorted the right part) instead of an optimal O(n).
1class Solution:
2 def partitionDisjoint(self, nums: List[int]) -> int:
3 # we can start with the first min(nums) if we want
4 pivot = 1
5 l_max = nums[0]
6
7 # for right, we keep track of how many times each value occurs, so that we know "this is the last `3` in the right"
8 r_dict = Counter(nums[1:])
9 # need a sorted list to quickly find the next smallest value in right
10 r_sorted = sorted(list(r_dict.keys())) # O(nlogn)
11 # need a pointer to skip further when next in list is already zero
12 r_sorted_ptr = 0
13 r_min = r_sorted[r_sorted_ptr]
14
15 while l_max > r_min:
16 # idea:
17 # put right[0] to left (we don't fully track left)
18 # 1. update l_max if it's the new largest in left
19 # 2. count -= 1 in right
20 # 3. check whether this is the current r_min
21 # 3.1 if so, check whether this is the last r_min in right
22 # 3.1.1 if so, iterate r_sorted_ptr until r_dict[r_sorted[r_sorted_ptr]] > 0
23 # that would be our new r_min
24 spotlight = nums[pivot]
25 if spotlight > l_max:
26 l_max = spotlight
27
28 r_dict[spotlight] -= 1
29 if spotlight == r_min and r_dict[spotlight] == 0:
30 while r_dict[r_sorted[r_sorted_ptr]] < 1:
31 r_sorted_ptr += 1
32 # our updated ptr will be the location of our new r_min
33
34 r_min = r_sorted[r_sorted_ptr]
35
36 pivot += 1
37
38 return pivot
For an O(n) method, we basically need a way to be able to check max_left and min_right in O(1).
1class Solution:
2 def partitionDisjoint(self, nums: List[int]) -> int:
3 n = len(nums)
4 max_l = [0] * n
5 min_r = [0] * n
6
7 max_l[0] = nums[0]
8 for i in range(1, n):
9 max_l[i] = max(max_l[i - 1], nums[i])
10
11 min_r[-1] = nums[-1]
12 for j in range(n - 2, -1, -1):
13 min_r[j] = min(min_r[j + 1], nums[j])
14
15 partition = 1
16 while max_l[partition - 1] > min_r[partition]:
17 partition += 1
18
19 return partition