Smallest Left Block Without Crossings
MediumArrays & Hashing
Problem
A warehouse wants to split the shelf nums into a non-empty left block and a non-empty right block so that every value in the left block is less than or equal to every value in the right block.
Return the length of the shortest left block that works. Such a split is guaranteed to exist.
Example 1
- Input:
- nums = [5, 0, 3, 8, 6]
- Output:
- 3
Left [5, 0, 3] has max 5, right [8, 6] has min 6. Shorter left blocks keep a 0 or 3 on the right.
Example 2
- Input:
- nums = [1, 1, 1, 0, 6, 12]
- Output:
- 4
Example 3
- Input:
- nums = [1, 2]
- Output:
- 1
Constraints
- 2 ≤ nums.length ≤ 10^5
- -10^6 ≤ nums[i] ≤ 10^6
- A valid split exists.
Hint
Show the first hint
For a split after index i, you only need two numbers: the max of the left part and the min of the right part.
Walkthrough
How to approach it
01Clarify before coding
- Must both blocks be non-empty? Yes.
- Is ≤ allowed across the split? Yes, equal values may sit on either side.
- Is a split guaranteed? Yes, no 'not found' value is needed.
02Brute force
For each split point, compute the left max and the right min from scratch.
Cost: O(n²) time, 10^10 steps at n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.