Pair-Sum O(N²) Timeout — Hash Map Fix for Array Interview

package io.thecodeforge.arrays;

import java.util.Arrays;

/**
 * TheCodeForge: Two-Pointer Implementation for Sorted Arrays.
 * Time Complexity: O(N) if sorted / O(N log N) if unsorted.
 */
public class TwoSumProvider {
    public int[] findTwoSum(int[] numbers, int target) {
        // In a real interview, always clarify if you should sort it yourself
        Arrays.sort(numbers);
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            if (currentSum == target) {
                return new int[]{left + 1, right + 1}; // Standard 1-based index return
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

package io.thecodeforge.arrays;

/**
 * io.thecodeforge implementation of Kadane's Algorithm.
 * Crucial for LeetCode Medium/Hard variations like 'Maximum Product Subarray'.
 */
public class MaxSubarray {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int maxSoFar = nums[0];
        int currentMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // The Forge Logic: Max(current element alone, current element + previous window)
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        return maxSoFar;
    }
}

package io.thecodeforge.arrays;

import java.util.HashMap;
import java.util.Map;

/**
 * TheCodeForge: Two Sum using Hash Map (unsorted array).
 * Time: O(N), Space: O(N)
 */
public class TwoSumHashMap {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

package io.thecodeforge.strings;

import java.util.HashMap;
import java.util.Map;

/**
 * TheCodeForge: Sliding window with HashMap for longest substring without repeating characters.
 * Works on any array of comparable elements.
 */
public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastIndex.containsKey(c)) {
                // Move left to one past the previous occurrence (if greater)
                left = Math.max(lastIndex.get(c) + 1, left);
            }
            lastIndex.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

package io.thecodeforge.arrays;

/**
 * TheCodeForge: Search in Rotated Sorted Array.
 * Time: O(log N), Space: O(1)
 */
public class SearchRotatedSortedArray {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            // Determine which half is sorted
            if (nums[low] <= nums[mid]) { // left half is sorted
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else { // right half is sorted
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}