package com.freetymekiyan.algorithms.level.medium;

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

/**
 * Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one,
 * return 0 instead.
 * <p>
 * Note:
 * The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
 * <p>
 * Example 1:
 * Given nums = [1, -1, 5, -2, 3], k = 3,
 * return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
 * <p>
 * Example 2:
 * Given nums = [-2, -1, 2, 1], k = 1,
 * return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
 * <p>
 * Follow Up:
 * Can you do it in O(n) time?
 * <p>
 * Company Tags: Palantir, Facebook
 * Tags: Hash Table
 * Similar Problems: (M) Minimum Size Subarray Sum, (E) Range Sum Query - Immutable
 */
public class MaximumSizeSubarraySumEqualsK {

    /**
     * Hash Table.
     * For 0 <= i < j < nums.length,
     * Find max(i, j) for sum[j] - sum[i-1] = k.
     * Except when i = 0, sum[j] = k.
     * The brute-force way is we loop through the array, keep updating sum.
     * Then subtract with each previous sum to see if it's k.
     * But previous sum is already calculated, and we can use a map to get it in O(1).
     * Use a hash table to store sum and its earliest index.
     */
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int sum = 0;
        map.put(0, -1); // Sum is 0 for index -1. Make sure sum[j] - sum[i-1] always works.
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) { // Search previous sums.
                res = Math.max(res, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) { // Keep only the smallest i
                map.put(sum, i);
            }
        }
        return res;
    }

}

@@ -98,16 +98,66 @@
 p;%0A%0A/**%0A
+ * 325. Maximum Size Subarray Sum Equals k%0A * %3Cp%3E%0A
  * Given
@@ -1010,12 +1010,13 @@
 max(
-i, j
+j - i
 ) fo
@@ -1108,18 +1108,18 @@
  way is 
-we
+to
  loop th
@@ -1149,16 +1149,22 @@
 pdating 
+total 
 sum.%0A   
@@ -1196,24 +1196,30 @@
 ch previous 
+total 
 sum to see i
@@ -1224,11 +1224,15 @@
  if 
-it'
+there i
 s k.
@@ -1256,14 +1256,22 @@
 ous 
-sum is
+total sums are
  alr
@@ -1289,13 +1289,21 @@
 ated
-, and
+.%0A     * Then
  we 
@@ -1323,18 +1323,20 @@
  to get 
-i
 t
+hem
  in O(1)
@@ -1386,22 +1386,125 @@
 its 
-earliest index
+EARLIEST index.%0A     * Note that we don't update the index of same sum because the length would definitely be smaller
 .%0A  
@@ -1590,19 +1590,26 @@
 nteger%3E 
-map
+sumToIndex
  = new H
@@ -1632,19 +1632,22 @@
     int 
-res
+maxLen
  = 0;%0A  
@@ -1669,27 +1669,34 @@
  0;%0A        
-map
+sumToIndex
 .put(0, -1);
@@ -1856,19 +1856,26 @@
     if (
-map
+sumToIndex
 .contain
@@ -1932,19 +1932,22 @@
         
-res
+maxLen
  = Math.
@@ -1954,20 +1954,30 @@
 max(
-res, i - map
+maxLen, i - sumToIndex
 .get
@@ -2019,19 +2019,26 @@
    if (!
-map
+sumToIndex
 .contain
@@ -2077,16 +2077,17 @@
 allest i
+.
 %0A       
@@ -2095,19 +2095,26 @@
         
-map
+sumToIndex
 .put(sum
@@ -2162,11 +2162,14 @@
 urn 
-res
+maxLen
 ;%0A  
@@ -2174,9 +2174,8 @@
     %7D%0A%0A%7D
-%0A

update 325. Maximum Size Subarray Sum Equals k with better explanation and naming