The Daily (Easy): `1752. Check if Array Is Sorted and Rotated`

Here is my solution:

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        diffs = [(nums[i] - nums[i-1]) < 0 for i in range(n)]
        # print(sum(diffs))

        return sum(diffs) == 1 or sum(diffs) == 0

in essence, you just make sure there’s only one inflection point (where the next item is greater than the prev, i.e., breaks monotonically increasing order), or there are no inflection points, i.e., all items are the same.

A greater challenge: `4. Median of Two Sorted Arrays`

At first I thought this was kinda like 210 where we maintain a max heap of all items less than median and min heap of all items greater than current median. But then the TC is $O((m + n) \log (m + n))$ which would just be the same as sorting and then taking the (m + n) // 2th element.

Since the TC needs to be $O(\log (m + n))$, the solution is sort sort of divide and conquer.

Scratchpad for my thoughts as I work:

cases (WLOG can swap nums1 and nums2)
W(m, n) = W(m // 2, n // 2) + O(1)
notice that log(m) + log(n) = log(mn) > log(m + n)

nums1 all leq nums2
=> nums1[-1] < nums2[0]
=> median findable easy

nums2 "wraps" nums1
=> nums2[-1] > nums1[-1] and nums1[0] > nums2[0]
=> again easy 

nums1 and nums2 are interleaved 
[1, 3, 5]
[2, 4, 6, 8, 10]
combined is [1, 2, 3, 4, 5, 6, 8, 10] -> med is 4.5 
this is the hella annoying one. 
(1, 5) and (2, 10) are the extremes
we need to cut out (3 + 5) // 2 = 4 elements.
the middles are 3 and 6, this would cut off 1 + 2 = 3 elements
that can't be it right?
since the middle of nums2 is greater than the hi of nums1,
... dunno

How can we split into subproblems where size decreases by a constant factor?

# m + n = 8
[1, 3, 5], [2, 4, 6, 8, 10] == [1, 2, 3, 4, 5, 6, 8, 10]
# m + n = 4
=> [3, 5], [4, 6] == [3, 4, 5, 6]
# m + n = 2
=> [5], [4] == [4, 5]
=> 4.5

What if the combined array has odd length? Remember we floor div 2 the overall size after each step

# m + n = 7
[1, 3, 5], [2, 4, 6, 8] == [1, 2, 3, 4, 5, 6, 8]
# m + n = 3
=> [3, 5], [4] == [3, 4, 5]
# m + n = 1
=> [], [4] == [4]
=> 4

Okay so let’s look at the extremes for the nums1 and nums2 arrays.

[1, 3, 5], [2, 4, 6, 8, 10] == [1, 2, 3, 4, 5, 6, 8, 10]
# true lo, hi = 1, 10
# @ lo1 = 0, lo2 = 0 == 1, 2
# @ hi1 = m - 1 = 2, hi2 = n - 1 = 4 == 5, 10 
# @ med1 = 1, med2 = 2 == 3, 6
# we want to move s.t.
=> [3, 5], [4, 6] == [3, 4, 5, 6]
# @ lo1' = 1 == med1, lo2' = 1 == 
# @ hi1' = 2 == hi1, hi2' = 2 == med2

not quite sure what to do with lo2'. But the overall gist should be:

compare the medians of nums1 and nums2
if the median of nums2 is bigger than the hi of nums1, we can throw out the upper half of nums2???

Rethinking…

No this can’t be right. Using the two medians of the subarrays is bad. What if we keep track of the items on left and right that we’ve ignored in the overall array?

# m + n = 3 + 5 = 8
# lo's of (0, 0) ignore 0 + 0 = 0
# hi's of (m-1, n-1) ignore 0 + 0 = 0
[1, 3, 5], [2, 4, 6, 8, 10] == [1, 2, 3, 4, 5, 6, 8, 10]
# m + n = 4
# lo's of (1, 1) ignore 1 + 1 = 2
# hi's of (2 = m-1-0, 5 = n-1-2 = n-3) ignore 0 + 2 = 2
=> [3, 5], [4, 6] == [3, 4, 5, 6]
# m + n = 2
# lo's ignore 2 + 1 = 3
# hi's ignore 0 + 3 = 3
=> [5], [4] == [4, 5]
=> 4.5

still not great… what the hell is the pattern?

We know that you may not be able to jump to the medians of both arrays right?

But if you get the medians of both subarrays, it’s not necessarily obvious how to update the lo and hi for each subarray. It seems annoying to reason about and not super helpful.

Maybe we can somehow strengthen the subproblem?

Again, the recurrence we want is $W(m+n) = W((m + n) / 2) + O(1)$, same recurrence as binary search.

We can strengthen the subproblem by passing in m, n, ignored_left, ignored_right

so let’s work through our two cases using this:

Odd Case:

# m = 3, n = 4, ignored_left = 0, ignored_right = 0
[1, 3, 5], [2, 4, 6, 8] == [1, 2, 3, 4, 5, 6, 8]
# m = 2, n = 1, ignored_left = 2, ignored_right = 2
=> [3, 5], [4] == [3, 4, 5]
# m = 0, n = 1, ignored_left = 3, ignored_right = 3
=> [], [4] == [4]
=> 4

Candidate invariant, ignored_left and ignored_right are equal.

Even Case:

# m = 3, n = 5, ignored_left = 0, ignored_right = 0
# lo1 = 0, lo2 = 0
# hi1 = 2, hi2 = 4
[1, 3, 5], [2, 4, 6, 8, 10] == [1, 2, 3, 4, 5, 6, 8, 10]

# m' = 2, n' = 2, ignored_left = 2, ignored_right = 2
# lo1 = 1, lo2 = 1
# hi1 = 2, hi2 = 2
=> [3, 5], [4, 6] == [3, 4, 5, 6]

# m'' = 1, n'' = 1, ignored_left = 3, ignored_right = 3
# lo1 = 1, lo2 = 2
# hi1 = 1, hi2 = 2
=> [5], [4] == [4, 5]
=> 4.5

The trouble is that ignored_left and ignored_right are computable from the original m and n. It’s also not any better than my previous idea.

Any sort of visual intuitions?

We can think of both of the nums arrays as being concatenated and slowly shrinking, and swapping positions as needed.

[1, 3, 5], [2, 4, 6, 8, 10] == [1, 2, 3, 4, 5, 6, 8, 10]
=> [3, 5], [4, 6] == [3, 4, 5, 6]
=> [5], [4] 
=> [4], [5] == [4, 5]
=> 4.5

[1, 3, 8], [2, 4, 5, 6, 10] == [1, 2, 3, 4, 5, 6, 8, 10]
=> [3], [4, 5, 6] == [3, 4, 5, 6]
=> [], [4, 5] == [4, 5]
=> 4.5

So clearly, we have an easy base case: if our left or right array is empty, return median of the other one.

However, the swapping logic is slightly complicated? We know nums1 needs to shrink by len(nums1) // 2 and nums2 needs to shrink by len(nums2) // 2, but we may not necessarily go to the median of either - we can take from either side.

There’s only one true way to do it such that it’s mathematically correct to maintain the median of the big overall combined array, however, it would be complicated to iterate through the possible ways to take from both sides. That would ruin our recurrence with $O(1)$ nonrecursive work per level.

Okay I’ll pack it up for the night,

spent about an hour and a half already…

The Daily (Easy): 1752. Check if Array Is Sorted and Rotated

A greater challenge: 4. Median of Two Sorted Arrays