Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Reverse Pairs

Problem (restated)

Count pairs i < j with nums[i] > 2 * nums[j].

Intuition

Walk right to left. For x = nums[i], count already-inserted values v with 2v < x, then insert x. A Fenwick tree of frequencies on compressed values answers that prefix: the first rank whose value has 2v ≥ x, minus one.

Approaches

Fenwick, query 2v < x

Unverified

Time O(n log n)Space O(n)

Idea. Unique-sort vals. From the right: ans += prefixSum(firstGe(x) - 1) where firstGe is the first index with 2 * vals[i] ≥ x; then update(rank(x), 1). Compare 2 * v in 64-bit.

Walkthrough. [1,3,2,3,1]. Pairs (1,4) → 3 > 2 and (3,4) → 3 > 2. Answer 2.

Trade-offs. Same skeleton as LC 315; only the query threshold changes. 2 * v overflows 32-bit (v up to 2^31-1). Merge-sort counting is the other standard solution.

Solution

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function reversePairs(nums: number[]): number {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const bit = new BIT(vals.length);
  const firstGe = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! * 2 < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  const rank = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  let ans = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    ans += bit.prefixSum(firstGe(nums[i]!) - 1);
    bit.update(rank(nums[i]!), 1);
  }
  return ans;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function reversePairs(nums: number[]): number {
  const vals = [...new Set(nums)].sort((a, b) => a - b);
  const bit = new BIT(vals.length);
  const firstGe = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! * 2 < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  const rank = (x: number): number => {
    let lo = 0, hi = vals.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid]! < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };
  let ans = 0;
  for (let i = nums.length - 1; i >= 0; i--) {
    ans += bit.prefixSum(firstGe(nums[i]!) - 1);
    bit.update(rank(nums[i]!), 1);
  }
  return ans;
}

Template connection

BIT frequency table, right-to-left, with a scaled predicate. LC 315 is v < x; this is 2v < x.

Reflection

Walk from the right. For the current x, count stored values with 2 * v < x, then insert x. The pair is i < j and nums[i] > 2 * nums[j].
2 * v overflows a 32-bit word. Compare in a wide integer. Equality does not count.
One element is 0. An increasing array is 0. Doubling a negative makes it smaller, and the order follows that.