Array Problems

Problem 1: Remove Duplicates from Sorted Array

Explanation:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Approach:

1. Two-Pointer Technique: Use two pointers, slow and fast. slow keeps track of the last unique element, while fast iterates through the array.
2. Copy Unique Elements: If nums[fast] is different from nums[slow], increment slow and copy the value of nums[fast].
3. Return Length: The first slow + 1 elements in nums are the unique elements.

Time & Space Complexity:

• Time Complexity: O(n), as we iterate through the array once.
• Space Complexity: O(1), since the array is modified in place.

Java Implementation:

public class RemoveDuplicatesSortedArray {
    /**
     * Removes duplicates from a sorted array in-place.
     * @param nums sorted input array
     * @return length of the array with unique elements
     * 
     * Time Complexity: O(n) - Iterates through the array once.
     * Space Complexity: O(1) - Modifies array in-place.
     */
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
    
    public static void main(String[] args) {
        int[] input = {1, 1, 2};
        int length = removeDuplicates(input);
        System.out.print("Output: [");
        for (int i = 0; i < length; i++) {
            System.out.print(input[i] + (i < length - 1 ? ", " : ""));
        }
        System.out.println("]");
    }
}

Example:

Input:

nums = [1,1,2]

Output:

[1, 2]

Edge Cases Considered:

• All elements are unique → The array remains unchanged.
• All elements are the same → Only one element remains.
• Empty array → Should return 0.

---

Problem 2: Maximum Subarray

Explanation:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Approach:

1. Kadane’s Algorithm: Maintain a running sum (currentSum) and update maxSum whenever currentSum exceeds maxSum.
2. Reset on Negative Sum: If currentSum becomes negative, reset it to 0 since a negative sum will only decrease future sums.
3. Return maxSum: This will contain the largest contiguous subarray sum.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the array once.
• Space Complexity: O(1), as only a few extra variables are used.

Java Implementation:

public class MaximumSubarray {
    /**
     * Finds the maximum sum of a contiguous subarray.
     * @param nums input array
     * @return maximum sum of contiguous subarray
     * 
     * Time Complexity: O(n) - Iterates through the array once.
     * Space Complexity: O(1) - Uses a few extra variables.
     */
    public static int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    public static void main(String[] args) {
        int[] input = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int output = maxSubArray(input);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:

6

Edge Cases Considered:

• All negative numbers → Should return the least negative number.
• All positive numbers → Should return sum of all numbers.
• Single element array → Should return that element itself.

---

Problem 3: Count Primes

Explanation:

Given an integer n, return the number of prime numbers that are strictly less than n.

Approach:

1. Sieve of Eratosthenes:
   • Create a boolean array isPrime of size n, initialized to true.
   • Start from 2, mark its multiples as false.
   • Repeat for the next smallest true value until sqrt(n).
2. Count Primes: Count the true values in isPrime.

Time & Space Complexity:

• Time Complexity: O(n log log n), as per the Sieve of Eratosthenes.
• Space Complexity: O(n), for storing the boolean array.

Java Implementation:

public class CountPrimes {
    /**
     * Counts the number of prime numbers less than n.
     * @param n upper bound
     * @return count of prime numbers less than n
     * 
     * Time Complexity: O(n log log n) - Efficient sieve approach.
     * Space Complexity: O(n) - Boolean array storage.
     */
    public static int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) count++;
        }
        return count;
    }
    
    public static void main(String[] args) {
        int n = 10;
        int output = countPrimes(n);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

n = 10

Output:

4

(Primes less than 10 are 2, 3, 5, 7)

Edge Cases Considered:

• n < 2 → Should return 0.
• n is a prime number → Should count up to n-1.
• Very large n → Algorithm remains efficient.

---

Problem 4: Product of Array Except Self

Explanation:

Given an integer array nums, return an array output where output[i] is equal to the product of all elements in nums except nums[i], without using division.

Approach:

1. Left and Right Product Arrays:
   • Compute leftProducts[] where leftProducts[i] is the product of all elements before index i.
   • Compute rightProducts[] where rightProducts[i] is the product of all elements after index i.
   • Multiply leftProducts[i] * rightProducts[i] to get output[i].
2. Optimized In-Place Computation:
   • Use a single output array, computing the left product in one pass.
   • Compute the right product in a second pass using a single variable.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the array twice.
• Space Complexity: O(1), if we ignore the output array.

Java Implementation:

public class ProductExceptSelf {
    /**
     * Computes the product of all elements except self.
     * @param nums input array
     * @return output array
     * 
     * Time Complexity: O(n) - Two-pass computation.
     * Space Complexity: O(1) - Uses output array only.
     */
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];
        
        // Compute left product
        output[0] = 1;
        for (int i = 1; i < n; i++) {
            output[i] = output[i - 1] * nums[i - 1];
        }
        
        // Compute right product and final result
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            output[i] *= right;
            right *= nums[i];
        }
        
        return output;
    }
    
    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4};
        int[] output = productExceptSelf(input);
        System.out.print("Output: [");
        for (int i = 0; i < output.length; i++) {
            System.out.print(output[i] + (i < output.length - 1 ? ", " : ""));
        }
        System.out.println("]");
    }
}

Example:

Input:

nums = [1,2,3,4]

Output:

[24, 12, 8, 6]

Edge Cases Considered:

• Contains zero → Zero should nullify product for that index.
• All elements are the same → Output follows a pattern.
• Single element array → Should return [1].

---

Problem 5: Merge Sorted Array

Explanation:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Approach:

1. Two-Pointer Approach: Start from the end of both arrays and place the largest element at the last position.
2. Decrement Pointers: Move backwards through nums1 and nums2 until all elements are merged.
3. Handle Remaining Elements: If elements remain in nums2, copy them into nums1.

Time & Space Complexity:

• Time Complexity: O(m + n), since we traverse both arrays once.
• Space Complexity: O(1), as we modify nums1 in place.

Java Implementation:

public class MergeSortedArray {
    /**
     * Merges two sorted arrays in place.
     * @param nums1 first sorted array with extra space at the end
     * @param m number of elements in nums1
     * @param nums2 second sorted array
     * @param n number of elements in nums2
     *
     * Time Complexity: O(m + n) - Iterates through both arrays once.
     * Space Complexity: O(1) - Modifies nums1 in-place.
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
    
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merge(nums1, 3, nums2, 3);
        System.out.println("Output: " + Arrays.toString(nums1));
    }
}

Example:

Input:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output:

[1,2,2,3,5,6]

Edge Cases Considered:

• nums2 is empty → nums1 remains unchanged.
• nums1 is empty → nums1 gets fully replaced by nums2.
• All elements in nums1 are smaller → Elements of nums2 are appended at the end.

---

Problem 6: Rotate Array

Explanation:

Given an integer array nums, rotate the array to the right by k steps.

Approach:

1. Reverse Entire Array: Reverse all elements.
2. Reverse First k Elements: Reverse the first k elements.
3. Reverse Remaining Elements: Reverse the remaining n - k elements.

Time & Space Complexity:

• Time Complexity: O(n), since we reverse the array three times.
• Space Complexity: O(1), as we modify nums in place.

Java Implementation:

public class RotateArray {
    /**
     * Rotates an array to the right by k steps.
     * @param nums input array
     * @param k number of steps to rotate
     *
     * Time Complexity: O(n) - Three reversals.
     * Space Complexity: O(1) - In-place modification.
     */
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        rotate(nums, k);
        System.out.println("Output: " + Arrays.toString(nums));
    }
}

Example:

Input:

nums = [1,2,3,4,5,6,7], k = 3

Output:

[5,6,7,1,2,3,4]

Edge Cases Considered:

• k is larger than nums.length → Use k %= nums.length to handle.
• All elements are the same → Rotation has no effect.
• Array of size 1 → Rotation has no effect.

---

Problem 7: Spiral Matrix

Explanation:

Given an m x n matrix, return all elements in spiral order.

Approach:

1. Four Boundaries: Maintain top, bottom, left, and right pointers.
2. Traverse in Spiral Order:
   • Move left to right along the top row.
   • Move top to bottom along the right column.
   • Move right to left along the bottom row (if not already traversed).
   • Move bottom to top along the left column (if not already traversed).
3. Adjust Boundaries: Shrink the boundaries as each layer is completed.
4. Stop Condition: When top > bottom or left > right.

Time & Space Complexity:

• Time Complexity: O(m * n), since every element is visited once.
• Space Complexity: O(1), since we modify the result in place.

Java Implementation:

import java.util.*;

public class SpiralMatrix {
    /**
     * Returns the elements of a matrix in spiral order.
     * @param matrix input 2D array
     * @return list of elements in spiral order
     *
     * Time Complexity: O(m * n) - Each element is visited once.
     * Space Complexity: O(1) - Uses only output list.
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) result.add(matrix[top][i]);
            top++;
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;
            if (top <= bottom) {
                for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        System.out.println("Output: " + spiralOrder(matrix));
    }
}

Example:

Input:

matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Output:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

Edge Cases Considered:

• Single row matrix → Traverse left to right.
• Single column matrix → Traverse top to bottom.
• Empty matrix → Return an empty list.
• Non-square matrix → Handles both cases correctly.

---

Problem 8: Maximum Product Subarray

Explanation:

Given an integer array nums, find the contiguous subarray within nums which has the largest product.

Approach:

1. Dynamic Tracking: Maintain two variables, maxProduct and minProduct, since a negative number can become positive when multiplied.
2. Iterate Through Array:
   • Calculate tempMax and tempMin to track possible new values.
   • Update maxProduct and minProduct based on the new computed values.
3. Keep Track of Result: Maintain a result variable to store the maximum value encountered.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the array once.
• Space Complexity: O(1), as only a few extra variables are used.

Java Implementation:

public class MaximumProductSubarray {
    /**
     * Finds the maximum product of a contiguous subarray.
     * @param nums input array
     * @return maximum product
     *
     * Time Complexity: O(n) - Iterates through the array once.
     * Space Complexity: O(1) - Uses a few extra variables.
     */
    public static int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        
        int maxProduct = nums[0], minProduct = nums[0], result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int tempMax = Math.max(nums[i], Math.max(maxProduct * nums[i], minProduct * nums[i]));
            int tempMin = Math.min(nums[i], Math.min(maxProduct * nums[i], minProduct * nums[i]));
            maxProduct = tempMax;
            minProduct = tempMin;
            result = Math.max(result, maxProduct);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] input = {2, 3, -2, 4};
        System.out.println("Output: " + maxProduct(input));
    }
}

Example:

Input:

nums = [2,3,-2,4]

Output:

6

Edge Cases Considered:

• All negative numbers → Should correctly track min and max products.
• Single element array → Should return that element itself.
• Zeros in the array → Should reset product calculations appropriately.

---

Problem 9: Find the Duplicate Number

Explanation:

Given an array nums containing n + 1 integers where each integer is between 1 and n inclusive, return the duplicate number.

Approach:

1. Floyd’s Tortoise and Hare (Cycle Detection):
   • Use slow and fast pointers to detect a cycle in the array.
   • Find the cycle’s entrance to locate the duplicate number.
2. Mathematical Sum Approach (Alternative): Use summation formula to find the missing number.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the array in linear time.
• Space Complexity: O(1), as only two pointers are used.

Java Implementation:

public class FindDuplicateNumber {
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println("Output: " + findDuplicate(nums));
    }
}

Example:

Input:

nums = [1,3,4,2,2]

Output:

2

Edge Cases Considered:

• Only one duplicate number but appears multiple times → The algorithm correctly identifies it.
• Duplicate number appears at the beginning or end → The cycle detection still works.
• All elements are the same → Should correctly return that element as the duplicate.
• Large array with many elements → The algorithm runs efficiently in O(n) time.
• Minimal case where n = 2 → Example: [1, 1] should return 1.

---

Problem 10: Trapping Rain Water

Explanation:

Given an array height representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Approach:

1. Two-Pointer Approach:
   • Maintain two pointers, left and right, starting at both ends.
   • Keep track of the leftMax and rightMax water levels.
2. Compare Heights:
   • If height[left] is smaller, compute trapped water at left and move the pointer.
   • Otherwise, compute trapped water at right and move the pointer.
3. Accumulate Water Volume: Sum the trapped water at each step until left and right meet.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the array once.
• Space Complexity: O(1), as only a few extra variables are used.

Java Implementation:

public class TrappingRainWater {
    public static int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
    
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println("Output: " + trap(height));
    }
}

Example:

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

Edge Cases Considered:

• Flat terrain (all heights the same) → Should return 0.
• No elevation (all heights are zero) → Should return 0.
• Single peak (no valleys to trap water) → Should return 0.
• Multiple peaks and valleys → Algorithm correctly accumulates water.
• Minimal case (array length of 2 or less) → Should return 0.

---

Problem 11: Move Zeroes

Explanation:

Given an integer array nums, move all 0s to the end while maintaining the relative order of non-zero elements.

Approach:

1. Two-pointer approach:
   • Use a pointer to track non-zero elements.
   • Swap elements to move zeros to the end while keeping order.

Time & Space Complexity:

• Time Complexity: O(n), as we traverse the array once.
• Space Complexity: O(1), since we modify the array in place.

Java Implementation:

public class MoveZeroes {
    /**
     * Moves all zeroes to the end while maintaining the order of non-zero elements.
     * @param nums - input array
     */
    public static void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[nonZeroIndex];
                nums[nonZeroIndex] = temp;
                nonZeroIndex++;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
        System.out.println("Output: " + java.util.Arrays.toString(nums));
    }
}

Example:

Input:

nums = [0, 1, 0, 3, 12]

Output:

[1, 3, 12, 0, 0]

Edge Cases Considered:

• All zeroes → Should remain in place.
• No zeroes → Should remain unchanged.
• Zeros at the beginning or end → Should handle correctly.

---

Problem 12: Triangle

Explanation:

Given a triangle array, return the minimum path sum from top to bottom, where each step moves to adjacent numbers on the next row.

Approach:

1. Bottom-Up Dynamic Programming:
   • Start from the second-last row and update values by adding the minimum of the two adjacent values below.
   • Modify the input array to save space.

Time & Space Complexity:

• Time Complexity: O(n²), as we traverse each element once.
• Space Complexity: O(1), since we modify the input array.

Java Implementation:

import java.util.List;

public class Triangle {
    /**
     * Computes the minimum path sum in a triangle.
     * @param triangle - list of integer lists representing the triangle
     * @return minimum path sum
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        for (int row = triangle.size() - 2; row >= 0; row--) {
            for (int col = 0; col < triangle.get(row).size(); col++) {
                triangle.get(row).set(col, triangle.get(row).get(col) +
                        Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
    
    public static void main(String[] args) {
        List<List<Integer>> triangle = List.of(
                List.of(2),
                List.of(3, 4),
                List.of(6, 5, 7),
                List.of(4, 1, 8, 3)
        );
        System.out.println("Output: " + minimumTotal(triangle));
    }
}

Example:

Input:

triangle = [
  [2],
  [3,4],
  [6,5,7],
  [4,1,8,3]
]

Output:

11

Edge Cases Considered:

• Single-element triangle → Should return that element.
• Large triangle → Should efficiently compute.
• All elements are equal → Should correctly sum the minimum path.

---

Problem 13: Partition Equal Subset Sum

Explanation:

Given a non-empty array nums, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Approach:

1. Dynamic Programming (Knapsack Problem):
   • Compute total sum. If it’s odd, return false.
   • Use a boolean DP array to check if a subset sum of total/2 exists.

Time & Space Complexity:

• Time Complexity: O(n * sum), where sum is total/2.
• Space Complexity: O(sum), using optimized 1D DP array.

Java Implementation:

public class PartitionEqualSubsetSum {
    /**
     * Determines if the array can be partitioned into two subsets of equal sum.
     * @param nums - input array
     * @return true if partition is possible, false otherwise
     */
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;
        sum /= 2;
        
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        
        for (int num : nums) {
            for (int j = sum; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[sum];
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println("Output: " + canPartition(nums));
    }
}

Example:

Input:

nums = [1, 5, 11, 5]

Output:

true

Edge Cases Considered:

• Odd total sum → Should return false.
• Smallest possible valid case → [1,1] should return true.
• Array with large numbers → Should still compute efficiently.

---