3719. Longest Balanced Subarray I

/**
 * Problem: LeetCode 3719 - Longest Balanced Subarray I
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int longestBalanced(int[] nums) {
        int n = nums.length;
        int maxLen = 0;

        // Use a visited timestamp array to track distinct values in O(1) without reallocations
        int[] lastSeen = new int[100001];

        for (int i = 0; i < n; i++) {
            // Prune search if remaining elements cannot exceed maxLen
            if (n - i <= maxLen) {
                break;
            }

            int distinctEven = 0;
            int distinctOdd = 0;
            int currentIteration = i + 1;

            for (int j = i; j < n; j++) {
                int val = nums[j];
                if (lastSeen[val] != currentIteration) {
                    lastSeen[val] = currentIteration;
                    if ((val & 1) == 0) {
                        distinctEven++;
                    } else {
                        distinctOdd++;
                    }
                }

                if (distinctEven == distinctOdd) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
}

"""
Problem: LeetCode 3719 - Longest Balanced Subarray I
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0

        # Using a timestamp array for O(1) distinct value checking
        last_seen = [0] * 100001

        for i in range(n):
            if n - i <= max_len:
                break

            distinct_even = 0
            distinct_odd = 0
            iteration = i + 1

            for j in range(i, n):
                val = nums[j]
                if last_seen[val] != iteration:
                    last_seen[val] = iteration
                    if val % 2 == 0:
                        distinct_even += 1
                    else:
                        distinct_odd += 1

                if distinct_even == distinct_odd:
                    max_len = max(max_len, j - i + 1)

        return max_len

/**
 * Problem: LeetCode 3719 - Longest Balanced Subarray I
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;

        vector<int> lastSeen(100001, 0);

        for (int i = 0; i < n; i++) {
            if (n - i <= maxLen) {
                break;
            }

            int distinctEven = 0;
            int distinctOdd = 0;
            int currentIteration = i + 1;

            for (int j = i; j < n; j++) {
                int val = nums[j];
                if (lastSeen[val] != currentIteration) {
                    lastSeen[val] = currentIteration;
                    if ((val & 1) == 0) {
                        distinctEven++;
                    } else {
                        distinctOdd++;
                    }
                }

                if (distinctEven == distinctOdd) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
};

/**
 * Problem: LeetCode 3719 - Longest Balanced Subarray I
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestBalanced = function(nums) {
    const n = nums.length;
    let maxLen = 0;

    const lastSeen = new Int32Array(100001);

    for (let i = 0; i < n; i++) {
        if (n - i <= maxLen) {
            break;
        }

        let distinctEven = 0;
        let distinctOdd = 0;
        const currentIteration = i + 1;

        for (let j = i; j < n; j++) {
            const val = nums[j];
            if (lastSeen[val] !== currentIteration) {
                lastSeen[val] = currentIteration;
                if ((val & 1) === 0) {
                    distinctEven++;
                } else {
                    distinctOdd++;
                }
            }

            if (distinctEven === distinctOdd) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }

    return maxLen;
};