PrefixSum

437. Path Sum III

Maintain a local max and global max, update the max with current value (starting a new array) or max + current value (continuous array).

T: O(n) S: O(1)

    public int maxSubArray(int[] nums) {
        int max = nums[0], curtmax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curtmax = Math.max(curtmax + nums[i], nums[i]);
            max = Math.max(max, curtmax);
        }
        return max;
    }

Solution 2: Divide and Conquer

Solution 3: DP

def maxSubArray(self, nums: List[int]) -> int:
    dp = [0 for i in range(len(nums))]
    dp[0] = nums[0]
    maxx = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
        maxx = max(dp[i], maxx)
    return maxx

Use prefix sum and store the count of sum in a hashmap. When map.containsKey(sum - k), it indicates that there is a subarray sum which equals k, add it to the result.

Add a record to map (map.put(0, 1)), this give the count between any number 0, in case that number equals k.

T: O(n) S: O(n)

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, result = 0;
    for (int n : nums) {
        sum += n;
        if (map.containsKey(sum - k)) {
            result += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return result;
}

Addition to LC560, store the minimum subarray lens before i which sums to target in a min array. When the previous minimum prevMin exists, it means there is a subarray sums to sum - target. That lens is i - prevMin. The result is the current min and previous min, which is i - prevMin + min[prevMin].

public int minSumOfLengths(int[] arr, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    int sum = 0;
    map.put(0, -1);
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        map.put(sum, i);
    }
    sum = 0;
    int one = Integer.MAX_VALUE, res = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (map.containsKey(sum - target)) {
            one = Math.min(one, i - map.get(sum - target));
        }
        if (map.containsKey(sum + target) && one != Integer.MAX_VALUE) {
            res = Math.min(res, one + (map.get(sum + target) - i));
        }
    }
    return res == Integer.MAX_VALUE ? -1 : res;
}

523. Continuous Subarray Sum

public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (k != 0) sum %= k;
        if (map.containsKey(sum)) {
            if (map.get(sum) < i - 1) return true;
        } else {
            map.put(sum, i);
        }
    }
    return false;
}

Prefix + HashMap and get the maximum interval.

public int maxSubArrayLen(int[] nums, int k) {
    if (nums == null || nums.length == 0) return 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0, res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - k)) {
            res = Math.max(res, i - map.get(sum - k)); 
        }
        if (!map.containsKey(sum)) map.put(sum, i);
    }
    return res;
}

Maintain both positive and negative values in two arrays, update with current min/max.

def maxSubArrayLen(self, nums: List[int], k: int) -> int:
    _dict = {}
    _dict[0] = -1
    _sum = 0
    _min = sys.maxsize
    for i in range(len(nums)):
        _sum += nums[i]
        if _sum - k in _dict:
            _min = min(_min, i - _dict[_sum - k])
        if _sum not in _dict:
            _dict[_sum] = i
    return 0 if _min == sys.maxsize else _min
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] pos = new int[n];
        int[] neg = new int[n];
        int max = nums[0];
        pos[0] = neg[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pos[i] = Math.max(Math.max(pos[i - 1] * nums[i], neg[i - 1] * nums[i]), 
                              nums[i]);
            neg[i] = Math.min(Math.min(pos[i - 1] * nums[i], neg[i - 1] * nums[i]),
                              nums[i]);
            max = Math.max(max, pos[i]);
        }
        return max;
    }

Maintain a prefix product. When encounter 0, reset the prefix product list.

Add: T: O(1), GetProduct: T: O(1)

List<Integer> list;
public ProductOfNumbers() {
    list = new ArrayList<>();
    list.add(1);
}

public void add(int num) {
    if (num > 0) {
        list.add(list.get(list.size() - 1) * num);   
    } else {
        list = new ArrayList<>();
        list.add(1);
    }
}

public int getProduct(int k) {
    if (k >= list.size()) return 0;
    return list.get(list.size() - 1) / list.get(list.size() - k - 1);
}

Last updated

Was this helpful?