Global and Local Inversions

MediumArrays & Hashingmath

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given nums, a permutation of the integers 0 to n - 1. A **global inversion** is a pair of indices i < j with nums[i] > nums[j]. A **local inversion** is an index i (with 0 <= i < n - 1) where nums[i] > nums[i + 1]. Every local inversion is also a global inversion. Return true if the number of global inversions equals the number of local inversions, and false otherwise. Aim for O(n) time.

Examples

Input: nums = [1,0,2]
Output: true
There is one global inversion `(0, 1)` and it is also the only local inversion.
Input: nums = [1,2,0]
Output: false
Global inversions are `(0, 2)` and `(1, 2)`, but only index 1 is a local inversion.

Constraints

  • `n == nums.length`
  • `1 <= n <= 10^5`
  • `nums` is a permutation of `0..n-1`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More math problems