3721. Longest Balanced Subarray II

Description

You are given an integer array nums.

A is called balanced if the number of distinct even numbers in the subarray is equal to the number of distinct odd numbers.

Return the length of the longest balanced subarray.

 

Example 1:

Input: nums = [2,5,4,3]

Output: 4

Explanation:

• The longest balanced subarray is [2, 5, 4, 3].
• It has 2 distinct even numbers [2, 4] and 2 distinct odd numbers [5, 3]. Thus, the answer is 4.

Example 2:

Input: nums = [3,2,2,5,4]

Output: 5

Explanation:

• The longest balanced subarray is [3, 2, 2, 5, 4].
• It has 2 distinct even numbers [2, 4] and 2 distinct odd numbers [3, 5]. Thus, the answer is 5.

Example 3:

Input: nums = [1,2,3,2]

Output: 3

Explanation:

• The longest balanced subarray is [2, 3, 2].
• It has 1 distinct even number [2] and 1 distinct odd number [3]. Thus, the answer is 3.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

 

Solutions

Solution: Segment Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const longestBalanced = function (nums) {
  const n = nums.length;
  const prevMap = new Map();
  const tree = new SegmentTree(n);
  let result = 0;

  for (let index = 0; index < n; index++) {
    const num = nums[index];
    const delta = num % 2 ? -1 : 1;

    if (prevMap.has(num)) {
      tree.update(0, prevMap.get(num), -delta);
    }

    tree.update(0, index, delta);
    prevMap.set(num, index);

    const l = tree.query();

    if (l !== -1 && l <= index) {
      const len = index - l + 1;

      result = Math.max(len, result);
    }
  }

  return result;
};

class SegmentTree {
  constructor(n) {
    this.n = n;
    this.minTree = Array.from({ length: 4 * n }, () => 0);
    this.maxTree = Array.from({ length: 4 * n }, () => 0);
    this.lazyTree = Array.from({ length: 4 * n }, () => 0);
  }

  sync(index, low, high) {
    const val = this.lazyTree[index];

    this.minTree[index] += val;
    this.maxTree[index] += val;

    if (low !== high) {
      this.lazyTree[index * 2 + 1] += val;
      this.lazyTree[index * 2 + 2] += val;
    }

    this.lazyTree[index] = 0;
  }

  update(l, r, delta) {
    this.#update(0, 0, this.n - 1, l, r, delta);
  }

  #update(index, low, high, l, r, delta) {
    this.sync(index, low, high);

    if (low > high || low > r || high < l) return;

    if (l <= low && r >= high) {
      this.lazyTree[index] += delta;
      this.sync(index, low, high);
      return;
    }

    const mid = Math.floor((low + high) / 2);

    this.#update(index * 2 + 1, low, mid, l, r, delta);
    this.#update(index * 2 + 2, mid + 1, high, l, r, delta);

    this.merge(this.minTree, index, (a, b) => Math.min(a, b));
    this.merge(this.maxTree, index, (a, b) => Math.max(a, b));
  }

  merge(tree, index, compare) {
    const a = tree[index * 2 + 1];
    const b = tree[index * 2 + 2];

    tree[index] = compare(a, b);
  }

  query() {
    return this.#query(0, 0, this.n - 1);
  }

  #query(index, low, high) {
    this.sync(index, low, high);

    if (this.minTree[index] > 0 || this.maxTree[index] < 0) return -1;

    if (low === high) {
      return this.minTree[index] === 0 ? low : -1;
    }

    const mid = Math.floor((low + high) / 2);
    const l = this.#query(index * 2 + 1, low, mid);

    if (l !== -1) return l;

    return this.#query(index * 2 + 2, mid + 1, high);
  }
}