8. Find Pivot Index

Problem: Given an integer array nums, find the pivot index where the sum of elements to the left equals the sum of elements to the right. If no such index exists, return -1.

Solution Approach: Single-pass traversal

class Solution {
    public int findPivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum * 2 == totalSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

---

9. Minimize Manhattan Distance

Problem: Given points on a 2D plane, remove exactly one point such that the maximum Manhattan distence among remaining points is minimized.

Solution Approach: Maintain maximum, second maximum, minimum, and second minimum values

class Solution {
    public int minimizeDistance(int[][] points) {
        final int MAX_VAL = Integer.MAX_VALUE;
        
        int maxFirst = -MAX_VAL, maxSecond = -MAX_VAL;
        int maxY1 = -MAX_VAL, maxY2 = -MAX_VAL;
        int minFirst = MAX_VAL, minSecond = MAX_VAL;
        int minY1 = MAX_VAL, minY2 = MAX_VAL;

        for (int[] pt : points) {
            int u = pt[0] + pt[1];
            int v = pt[1] - pt[0];

            if (u > maxFirst) {
                maxSecond = maxFirst;
                maxFirst = u;
            } else if (u > maxSecond) {
                maxSecond = u;
            }

            if (u < minFirst) {
                minSecond = minFirst;
                minFirst = u;
            } else if (u < minSecond) {
                minSecond = u;
            }

            if (v > maxY1) {
                maxY2 = maxY1;
                maxY1 = v;
            } else if (v > maxY2) {
                maxY2 = v;
            }

            if (v < minY1) {
                minY2 = minY1;
                minY1 = v;
            } else if (v < minY2) {
                minY2 = v;
            }
        }

        int result = MAX_VAL;
        for (int[] pt : points) {
            int u = pt[0] + pt[1];
            int v = pt[1] - pt[0];
            
            int deltaX = (u == maxFirst ? maxSecond : maxFirst) - 
                         (u == minFirst ? minSecond : minFirst);
            int deltaY = (v == maxY1 ? maxY2 : maxY1) - 
                         (v == minY1 ? minY2 : minY1);
            
            result = Math.min(result, Math.max(deltaX, deltaY));
        }
        return result;
    }
}

---

10. Count Incremovable Subarrays I

Problem: Given a positive integer array, count the number of subarrays whose removal results in a strictly increasing remaining array.

Solution Approach: Two pointers

class Solution {
    public int countIncremovableSubarrays(int[] nums) {
        int left = 0, len = nums.length;
        
        while (left + 1 < len && nums[left] < nums[left + 1]) {
            left++;
        }
        
        if (left == len - 1) {
            return len * (len + 1) / 2;
        }
        
        int result = left + 2;
        
        for (int right = len - 1; right > 0; right--) {
            while (left >= 0 && nums[left] >= nums[right]) {
                left--;
            }
            result += left + 2;
            
            if (nums[right - 1] >= nums[right]) {
                break;
            }
        }
        return result;
    }
}

---

11. Count Incremovable Subarrays II

Problem: Same as above but with larger constraints.

Solution Approach: Two pointers with O(n) complexity

class Solution {
    public long countIncremovableSubarrays(int[] arr) {
        int len = arr.length;
        int ptr = 0;
        
        while (ptr < len - 1 && arr[ptr] < arr[ptr + 1]) {
            ptr++;
        }
        
        if (ptr == len - 1) {
            return (long) len * (len + 1) / 2;
        }

        long answer = ptr + 2;
        
        for (int k = len - 1; k == len - 1 || arr[k] < arr[k + 1]; k--) {
            while (ptr >= 0 && arr[ptr] >= arr[k]) {
                ptr--;
            }
            answer += ptr + 2;
        }
        return answer;
    }
}

---

12. Minimum Number Game

Problem: Given an even-length array, players alternately remove the minimum element. Bob adds his removed element first, then Alice adds hers. Return the final array.

Solution Approach: Simulation with priority queue

class Solution {
    public int[] playGame(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int val : nums) {
            minHeap.offer(val);
        }
        
        int[] output = new int[nums.length];
        int index = 0;
        
        while (!minHeap.isEmpty()) {
            int first = minHeap.poll();
            output[index++] = minHeap.poll();
            output[index++] = first;
        }
        return output;
    }
}

---

13. Can Make Array Sorted

Problem: Determine if an array can be sorted by swapping adjacent elements that have the same number of 1-bits in their binary representation.

Solution Approach: Sort by bit-count groups

class Solution {
    public boolean canSortArray(int[] nums) {
        int length = nums.length;
        
        for (int i = 0; i < length; ) {
            int start = i;
            int bitCount = Integer.bitCount(nums[i++]);
            
            while (i < length && Integer.bitCount(nums[i]) == bitCount) {
                i++;
            }
            Arrays.sort(nums, start, i);
        }
        
        for (int i = 1; i < length; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

---

14. Max Increase to Keep City Skyline

Problem: Given an n×n grid representing building heights, increase building heights without changing the skyline from any direction. Find the maximum total increase possible.

Solution Approach: Greedy calculation using row and column maximums

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int[] rowHeights = new int[rows];
        int[] colHeights = new int[cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                rowHeights[i] = Math.max(rowHeights[i], grid[i][j]);
                colHeights[j] = Math.max(colHeights[j], grid[i][j]);
            }
        }

        int totalIncrease = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                totalIncrease += Math.min(rowHeights[i], colHeights[j]) - grid[i][j];
            }
        }
        return totalIncrease;
    }
}