From Quadratic to Linear: a Medium LeetCode Problem
Problem statement: https://leetcode.com/problems/global-and-local-inversions/description/
We have some permutation
A of [0, 1, ..., N - 1], where N is the length of A.
The number of (global) inversions is the number of
i < j with 0 <= i < j < N and A[i] > A[j].
The number of local inversions is the number of
i with 0 <= i < N and A[i] > A[i+1].
Return
true if and only if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: A = [1,0,2] Output: true Explanation: There is 1 global inversion, and 1 local inversion.
Example 2:
Input: A = [1,2,0] Output: false Explanation: There are 2 global inversions, and 1 local inversion.If you were like me the first solution that comes to mind is a straightforward count:
- Count local inversions
- Now, count global inversions
- Compare
Only one problem, though: it is N^2, and since the N=5000, this is 25,000,000 iterations, and the LeetCode gods don't like it:
There are two options now, either go with NLogN (some sort of variation of QuickSort or MergeSort), or we need to think about a Dynamic Programming (DP) like solution. Let's think about the problem....
A local inversion is by definition a global inversion. But not all global inversions are local inversions.
Therefore, all we need to do is to find a global inversion that is not a local inversion. If we find one, then for sure we'll have more global inversions than local inversions. If we don't find, they are the same.
A global inversion that is not a local inversion is one where A[i] > A[j] for some (any) i < j - 1. In other words, find a number in the array that is greater than another number to its right that is not adjacent to itself.
To do so here is the approach: keep track of the MAX number seen so far to the left of index "i". Then check whether MAX is greater than A[i+1]. If so, you found a global inversion that is NOT a local inversion and as such you should return false.
See it does not matter where MAX is, as long as it is located to the left of "i" (not including "i" itself).
Then as you move "i" you discard the previous MAX and have a new MAX.
One pass - linear solution.
To explain this logic in English took way longer than writing the code... Cheers, Marcelo.
public bool IsIdealPermutation(int[] A)
{
int maxBeforeCurrent = Int32.MinValue;
for (int i = 0; i < A.Length; i++)
{
if (i + 1 < A.Length && maxBeforeCurrent > A[i + 1]) return false;
maxBeforeCurrent = A[i] > maxBeforeCurrent ? A[i] : maxBeforeCurrent;
}
return true;
}
Rust one-liner :)
ReplyDeleteimpl Solution {
pub fn is_ideal_permutation(a: Vec) -> bool {
a.iter().enumerate().all(|(idx, val)| (idx as i32 - val).abs() <= 1)
}
}