LeetCode: Global And Local Inversions Solution

1/*
2  local inversions are subset of global inversion
3  so meanwhile
4    global: i < j where A[i] > A[j]
5    local:  i     where A[i] > A[i + 1]
6  then, local equals global when there is no A[i] > A[j = i + 2]
7*/
8
9/**
10 * @param {number[]} A
11 * @return {boolean}
12 */
13// O(N^2)
14var isIdealPermutation = function (A) {
15  const N = A.length
16  let [globalInversions, localInversions] = [0, 0]
17  for (let i = 0; i < N; i++) {
18    if (i + 1 < N && A[i] > A[i + 1]) {
19      localInversions++
20    }
21    for (let j = i + 1; j < N; j++) {
22      if (A[i] > A[j]) {
23        globalInversions++
24      }
25    }
26  }
27  return globalInversions === localInversions
28}
29
30// O(N)
31var isIdealPermutation = function (A) {
32  const N = A.length
33  let max = 0
34  for (let i = 0; i < N - 2; i++) {
35    max = Math.max(max, A[i])
36    if (max > A[i + 2]) {
37      return false
38    }
39  }
40  return true
41}