Data Structures19 sections · 729 units
Open in Course

Problem - Global and Local Inversions

BIT for counting

Given an integer array AA of length nn, return true if the number of global inversions equals the number of local inversions.

A global inversion is a pair (i,j)(i, j) where i<ji < j and A[i]>A[j]A[i] > A[j]. A local inversion is an index ii where A[i]>A[i+1]A[i] > A[i + 1]. Every local inversion is a global inversion.

The question asks: are all global inversions local? Use BIT to count global inversions, then check if it equals the local count. Constraints: nn up to 10510^5.