LeetCode 2395 - Find Subarrays With Equal Sum

The problem asks us to determine whether there exist two contiguous subarrays of length 2 in a given array nums that have the same sum. A subarray of length 2 is simply any consecutive pair of elements in the array.

leetcodeeasyarrayhash-table

LeetCode Problem 2395

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to determine whether there exist two contiguous subarrays of length 2 in a given array nums that have the same sum. A subarray of length 2 is simply any consecutive pair of elements in the array. The two subarrays must begin at different indices, which means even if they have identical elements, they are considered different if their positions in the array differ.

The input nums is a list of integers with length between 2 and 1000, and each integer can range from -10^9 to 10^9. The output is a boolean, true if at least two subarrays of length 2 have equal sum, and false otherwise.

Important edge cases include arrays where all elements are the same, arrays with negative numbers, and arrays with the minimum length of 2. The constraints guarantee that we always have at least one subarray of length 2, so we do not need to handle empty arrays or arrays with length less than 2.

Approaches

The brute-force approach would be to compute the sum of every possible subarray of length 2 and then check all pairs of sums to see if any two are equal. While this works, it requires examining O(n^2) pairs, which is inefficient for larger arrays.

The key observation for an optimal solution is that we only need to track sums of subarrays of length 2 as we iterate through the array once. By using a hash set to store each sum as it is computed, we can check in O(1) time whether we have seen the same sum before. This reduces the time complexity to O(n) and only requires O(n) additional space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Compute all pairs of subarray sums and compare them
Optimal O(n) O(n) Use a hash set to track sums of length-2 subarrays while iterating

Algorithm Walkthrough

  1. Initialize an empty hash set seen_sums to store the sums of length-2 subarrays.
  2. Iterate through the array from index 0 to len(nums) - 2. Each index i represents the starting position of a length-2 subarray.
  3. Compute the sum of the current subarray as current_sum = nums[i] + nums[i+1].
  4. Check if current_sum already exists in seen_sums. If it does, return true immediately, because we have found two subarrays with equal sum.
  5. If current_sum is not in seen_sums, add it to the set.
  6. Continue to the next index and repeat steps 3-5.
  7. If the iteration completes without finding any duplicate sums, return false.

Why it works: Each subarray sum is checked exactly once against all previously computed sums using the hash set. The set ensures that we detect duplicates efficiently. The correctness is guaranteed because we examine every contiguous pair, and any repeated sum will be detected immediately.

Python Solution

from typing import List

class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        seen_sums = set()
        for i in range(len(nums) - 1):
            current_sum = nums[i] + nums[i + 1]
            if current_sum in seen_sums:
                return True
            seen_sums.add(current_sum)
        return False

The Python implementation uses a set seen_sums to store the sums of each length-2 subarray. The loop iterates through the array until the second-to-last element to avoid index out-of-range errors. At each step, it computes the sum of the current pair and checks whether it has been seen before. If so, it returns true; otherwise, it adds the sum to the set and continues. If no duplicate sums are found, the function returns false.

Go Solution

func findSubarrays(nums []int) bool {
    seenSums := make(map[int]struct{})
    for i := 0; i < len(nums)-1; i++ {
        currentSum := nums[i] + nums[i+1]
        if _, exists := seenSums[currentSum]; exists {
            return true
        }
        seenSums[currentSum] = struct{}{}
    }
    return false
}

In Go, we use a map seenSums with empty struct values to mimic a set. The loop iterates through the array in the same manner. The sum of each consecutive pair is computed, and we check whether it exists in the map. The empty struct as the value type is memory-efficient since we only need the keys.

Worked Examples

Example 1: nums = [4,2,4]

i Subarray Sum seen_sums Return?
0 [4,2] 6 {} No
1 [2,4] 6 {6} Yes

Example 2: nums = [1,2,3,4,5]

i Subarray Sum seen_sums Return?
0 [1,2] 3 {} No
1 [2,3] 5 {3} No
2 [3,4] 7 {3,5} No
3 [4,5] 9 {3,5,7} No
End - - {3,5,7,9} False

Example 3: nums = [0,0,0]

i Subarray Sum seen_sums Return?
0 [0,0] 0 {} No
1 [0,0] 0 {0} Yes

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each subarray of length 2 is considered once, and hash set operations are O(1)
Space O(n) At most n-1 sums stored in the hash set

The algorithm iterates through the array once, performing constant-time operations for each pair. Space usage is linear in the worst case when no sums are repeated.

Test Cases

# Provided examples
assert Solution().findSubarrays([4,2,4]) == True  # duplicate sum 6
assert Solution().findSubarrays([1,2,3,4,5]) == False  # no duplicate sums
assert Solution().findSubarrays([0,0,0]) == True  # duplicate sum 0

# Edge cases
assert Solution().findSubarrays([1,1]) == False  # minimum size array, only one subarray
assert Solution().findSubarrays([1,-1,1,-1]) == True  # alternating sums 0
assert Solution().findSubarrays([1000000000,-1000000000,0,0]) == True  # large values, duplicate sum 0
assert Solution().findSubarrays([-5,-5,-5,-5]) == True  # negative numbers
assert Solution().findSubarrays([1,2,3,2,1]) == True  # repeated sums 3+2=5
Test Why
[4,2,4] Simple duplicate sum
[1,2,3,4,5] No duplicates, normal case
[0,0,0] Duplicate sum of zeros
[1,1] Minimum length array, only one subarray
[1,-1,1,-1] Alternating sums that repeat
[1000000000,-1000000000,0,0] Large numbers to test integer range
[-5,-5,-5,-5] Negative numbers repeating
[1,2,3,2,1] Duplicate sum not adjacent

Edge Cases

The first edge case is when the array has exactly two elements. In this scenario, only one subarray exists, so the function should correctly return false. The implementation handles this naturally because the loop range len(nums)-1 is 1, and no duplicate sum is possible.

The second edge case involves negative numbers or a mix of positive and negative numbers. For example, [-5,-5,-5,-5] produces repeated sums of -10. The solution handles this correctly because sums are stored in a hash set and negative numbers pose no issue for equality checking.

The third edge case is when the array contains very large or very small integers, testing integer overflow. In Python, integers are arbitrary precision, so overflow is not a concern. In Go, integer sums could exceed int bounds if the numbers were larger, but with the problem constraint of -10^9 to 10^9, the sum of two elements fits safely within a 32-bit or 64-bit integer. The implementation accounts for this by using the standard int type in Go.