algoadvance

Leetcode 2395. Find Subarrays With Equal Sum

Problem Statement

You are given a 0-indexed integer array nums. You need to find if there are at least two subarrays of length 2 with equal sum. Return true if such subarrays exist and false otherwise.

Example

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of length 2 have the same sum.

Clarifying Questions

  1. Q: What is the length constraints of the array nums?
    • A: The length of the array nums can be between 1 and 1000.
  2. Q: Can the elements in nums be negative?
    • A: The problem statement does not specify, so we assume nums can include negative numbers.
  3. Q: Will nums always have at least 2 elements?
    • A: The problem constraints imply this, but let’s confirm our understanding for edge cases.

Strategy

  1. Iterate through the array and calculate the sum of every possible subarray of length 2.
  2. Store the sums in a HashSet. HashSet allows for O(1) average-time complexity for insertions and lookups.
  3. If we encounter a sum that already exists in the HashSet, return true.
  4. If we finish iterating through the array without hitting duplicates, return false.

Code

import java.util.HashSet;
import java.util.Set;

public class SubarraysWithEqualSum {
    
    public boolean findSubarraysWithEqualSum(int[] nums) {
        Set<Integer> sums = new HashSet<>();
        
        for (int i = 0; i < nums.length - 1; i++) {
            int sum = nums[i] + nums[i + 1];
            if (!sums.add(sum)) {
                // sums.add(sum) returns false if the sum already exists in the set
                return true;
            }
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        SubarraysWithEqualSum solution = new SubarraysWithEqualSum();
        int[] nums1 = {4, 2, 4};
        int[] nums2 = {1, 2, 3, 4, 5};
        
        System.out.println(solution.findSubarraysWithEqualSum(nums1)); // true
        System.out.println(solution.findSubarraysWithEqualSum(nums2)); // false
    }
}

Time Complexity

This implementation ensures efficient time complexity while leveraging a HashSet to detect duplicate sums of subarrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI