Problems

Data Partitioning

Given an integer array nums of even length, split it into two arrays nums1 and nums2, such that:

• nums1.length == nums2.length == nums.length / 2
• Both nums1 and nums2 contain unique elements.

Return true if the array can be partitioned in this way, otherwise return false.

Approach

Use a hash map to count occurrences of each element. If any number appears more than twice, the splits impossible.

class Solution {
    public boolean canSplitArray(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            int freq = countMap.getOrDefault(num, 0);
            if (freq >= 2) {
                return false;
            }
            countMap.put(num, freq + 1);
        }
        return true;
    }
}

Maximum Square Area in Overlapping Rectangles

On a 2D plane, there are n rectangles defined by their bottom-left and top-right coordinates. Find the maximum area of a square that fits inside the intersection region of any two rectangles.

Approach

Iterate through all pairs of rectangles and compute the overlapping region. Determine the largest square that can fit within that region based on the minimum of width and height.

class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        long maxArea = 0;
        int n = bottomLeft.length;
        for (int i = 0; i < n; i++) {
            int[] bl1 = bottomLeft[i];
            int[] tr1 = topRight[i];
            for (int j = i + 1; j < n; j++) {
                int[] bl2 = bottomLeft[j];
                int[] tr2 = topRight[j];
                long area = calculateOverlapArea(bl1, tr1, bl2, tr2);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }

    private long calculateOverlapArea(int[] bl1, int[] tr1, int[] bl2, int[] tr2) {
        int overlapWidth = Math.max(0, Math.min(tr1[0], tr2[0]) - Math.max(bl1[0], bl2[0]));
        int overlapHeight = Math.max(0, Math.min(tr1[1], tr2[1]) - Math.max(bl1[1], bl2[1]));
        long side = Math.min(overlapWidth, overlapHeight);
        return side * side;
    }
}

Earliest Second to Mark All Indices I

Given two 1-indexed arrays nums and changeIndices, determine the earliest second when all indices in nums can be marked.

Each second s, you may:

• Decrease nums[i] by 1.
• If nums[changeIndices[s]] == 0, mark that index.
• Do nothing.

Return the earliest second, or -1 if impossible.

Approach

Binary search on time combined with simulation to validate whether a given time allows marking all indices.

class Solution {
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.length;
        int m = changeIndices.length;
        if (n > m) return -1;

        int[] lastTime = new int[n];
        int left = n - 1, right = m + 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (canMarkAll(nums, changeIndices, lastTime, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right > m ? -1 : right;
    }

    private boolean canMarkAll(int[] nums, int[] changeIndices, int[] lastTime, int maxSeconds) {
        Arrays.fill(lastTime, -1);
        for (int t = 0; t < maxSeconds; t++) {
            lastTime[changeIndices[t] - 1] = t;
        }

        for (int t : lastTime) {
            if (t < 0) return false;
        }

        int availableOps = 0;
        for (int i = 0; i < maxSeconds; i++) {
            int idx = changeIndices[i] - 1;
            if (i == lastTime[idx]) {
                if (nums[idx] > availableOps) return false;
                availableOps -= nums[idx];
            } else {
                availableOps++;
            }
        }
        return true;
    }
}

Earliest Second to Mark All Indices II

Similar to the previous problem, but now you can also set nums[changeIndices[s]] to any non-negative value.

Approach

Binary search with greedy strategy using a priority queue to optimize resource allocation.

class Solution {
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.length;
        int m = changeIndices.length;
        if (n > m) return -1;

        long totalWork = n;
        for (int v : nums) totalWork += v;

        int[] firstTime = new int[n];
        Arrays.fill(firstTime, -1);
        for (int t = m - 1; t >= 0; --t) {
            firstTime[changeIndices[t] - 1] = t;
        }

        PriorityQueue pq = new PriorityQueue((a, b) -> a[0] - b[0]);
        int left = n - 1, right = m + 1;
        while (left + 1 < right) {
            pq.clear();
            int mid = (left + right) / 2;
            if (canMarkAllII(nums, changeIndices, firstTime, pq, totalWork, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right > m ? -1 : right;
    }

    private boolean canMarkAllII(int[] nums, int[] changeIndices, int[] firstTime, PriorityQueue pq, long totalWork, int maxSeconds) {
        int availableOps = 0;
        for (int t = maxSeconds - 1; t >= 0; t--) {
            int i = changeIndices[t] - 1;
            int val = nums[i];
            if (val