# LeetCode: Global And Local Inversions Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/*2  local inversions are subset of global inversion3  so meanwhile4    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[]} A11 * @return {boolean}12 */13// O(N^2)14var isIdealPermutation = function (A) {15  const N = A.length16  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 === localInversions28}29
30// O(N)31var isIdealPermutation = function (A) {32  const N = A.length33  let max = 034  for (let i = 0; i < N - 2; i++) {35    max = Math.max(max, A[i])36    if (max > A[i + 2]) {37      return false38    }39  }40  return true41}```

leetcode

array

math

## Next Post

LeetCode: Determine If String Halves Are Alike

Apr 7, 2021

Search Posts