Subarray Sum Equals K

To find the total number of contiguous subarrays whose sum equals to ( k ), you can use a hash map to keep track of the prefix sum and its count. Here’s the code to solve the problem, followed by an explanation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        prefix_sum = 0
        sum_count = {0: 1}

        for num in nums:
            prefix_sum += num
            if prefix_sum - k in sum_count:
                count += sum_count[prefix_sum - k]
            sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1

        return count

Explanation

1. Initialize Variables: Initialize a variable count to keep track of the number of subarrays whose sum is ( k ), and prefix_sum to keep track of the current prefix sum. sum_count is a dictionary that stores the frequency of prefix sums.
2. Iterate Through the Array: For each number num in nums, calculate the prefix sum.
3. Check for Subarray Sum: If prefix_sum - k exists in sum_count, it means a subarray with sum ( k ) has been found. Increment the count by the value associated with prefix_sum - k.
4. Update Prefix Sum Count: Increment the count of prefix_sum in sum_count.
5. Return Result: Return the count.

Insights

• Prefix Sum: A prefix sum helps to efficiently calculate the sum of a subarray by keeping track of the sum of elements up to the current index.
• Hash Map: By using a hash map, you can quickly look up the count of specific prefix sums, improving the time complexity.

The time complexity of this solution is ( O(n) ), where ( n ) is the length of the array nums, as it iterates through the array once. The space complexity is also ( O(n) ), due to the storage required for the sum_count hash map.

Define the Terms

Define the Interface

Analyze the Input and Output Input need not be sorted. We can have duplicates

Identify the Invariants

Identify the constraints

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

Key Takeaways

0 1 2

 v

[1,1,1] ^ [1] [1,1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

 def subarray_sum(nums, k)
  counter = 0
#   invariant: j cannot be less than i 
  for i in (0..nums.size-1)
      sum = 0
      for j in (i..nums.size-1)
         sum += nums[j]

          if sum == k
             counter += 1 
          end
      end
  end

   counter
end

1. Prefix array
2. Sliding window

TLE: If you want to gain performance, what can you trade to gain performance.

Hash

Two Sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}

def subarray_sum(nums, k)
  counter = 0
  sum = 0
  hash = Hash.new(0)
  hash[0] = 1
  
  for i in (0..nums.size - 1)
     sum += nums[i]
     
     if hash.key?(sum - k)
         counter += hash[sum - k]
     end
     hash[sum] = hash[sum] + 1
  end
  
  counter
end

Identifying Problem Isomorphism

“Subarray Sum Equals K” asks us to find the number of continuous subarrays in a given array that equal a target sum.

An isomorphic problem to this is “930. Binary Subarrays With Sum”. In this problem, you’re given a binary array (an array that contains only 0s and 1s) and a target sum, and you need to find the number of non-empty subarrays that sum to the target.

The isomorphism here is: both problems require us to find contiguous subarrays in an array that sum up to a certain target. The only difference is that in the “930. Binary Subarrays With Sum” problem, we’re working with a binary array, while in the “560. Subarray Sum Equals K” problem, there are no restrictions on the array’s contents. The primary shared idea is identifying contiguous subarrays that sum to a specific target.

Problem 560, “Subarray Sum Equals K”, is about finding the total number of continuous subarrays whose sum equals a given integer. It’s a classic problem that involves understanding of array manipulation and prefix sums. Here’s a summary of the problem statement:

Prereqs

Given an array of integers and an integer K, you need to find the total number of continuous subarrays whose sum equals to K.

Example:

Input: nums = [1,1,1], k = 2
Output: 2

Constraints:

• The length of the array is in range [1, 20,000].
• The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

10 Prerequisite LeetCode Problems

Before you solve “Subarray Sum Equals K”, familiarize yourself with simpler problems related to arrays and prefix sums, such as:

1. “Running Sum of 1d Array” (LeetCode 1480)
2. “Richest Customer Wealth” (LeetCode 1672)
3. “Shuffle the Array” (LeetCode 1470)
4. “Number of Good Pairs” (LeetCode 1512)
5. “Find Numbers with Even Number of Digits” (LeetCode 1295)
6. “Find N Unique Integers Sum up to Zero” (LeetCode 1304)
7. “Decompress Run-Length Encoded List” (LeetCode 1313)
8. “Cells with Odd Values in a Matrix” (LeetCode 1252)
9. “How Many Numbers Are Smaller Than the Current Number” (LeetCode 1365)
10. “Check If N and Its Double Exist” (LeetCode 1346)

These cover how to handle arrays and manipulate their data to achieve a certain goal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
	def subarraySum(self, nums: List[int], k: int) -> int:
		ans=0
		prefsum=0
		d={0:1}

		for num in nums:
			prefsum = prefsum + num

			if prefsum-k in d:
				ans = ans + d[prefsum-k]

			if prefsum not in d:
				d[prefsum] = 1
			else:
				d[prefsum] = d[prefsum]+1

		return ans

Problem Classification

Language Agnostic Coding Drills

1. Understanding Variables: The knowledge of what variables are and how to initialize and use them.
2. Understanding Arrays/Lists: The knowledge of arrays or lists and how to manipulate them.
3. For Loops: Understanding how to use ‘for’ loops for iterating over an array/list.
4. Understanding Dictionary: Understanding the concept of dictionaries in python, how to declare them and how to add, retrieve and modify elements.
5. Conditional Statements (if-else): Understanding how to use ‘if’ conditions to control flow of the program.
6. Return Statement: Knowing how to use the return statement to provide outputs for functions.
7. Arithmetic Operations: Basic operations like addition and subtraction.
8. Understanding Functions: Declaring and defining functions in python.
9. Understanding Classes: Declaring classes and defining methods within classes.

In terms of difficulty, the progression:

1. Understanding Variables
2. Arithmetic Operations
3. Understanding Arrays/Lists
4. For Loops
5. Conditional Statements (if-else)
6. Understanding Dictionary
7. Return Statement
8. Understanding Functions
9. Understanding Classes

Targeted Drills in Python

1. Understanding Variables

   Drill: Create a variable named “number” and assign it the value 5. Then, print the value of “number”.

   1 2	number = 5 print(number)

2. Arithmetic Operations

   Drill: Add two numbers and store the result in a variable named “result”. Print the value of “result”.

   1 2 3 4

   number1 = 10 number2 = 15 result = number1 + number2 print(result)

3. Understanding Arrays/Lists

   Drill: Create a list of five numbers. Print the first and last elements of the list.

   1 2 3

   numbers = [1, 2, 3, 4, 5] print(numbers[0]) # First element print(numbers[-1]) # Last element

4. For Loops

   Drill: Create a for loop that prints each number in the previously created list.

   1 2	for number in numbers: print(number)

5. Conditional Statements (if-else)

   Drill: Check if the sum of the first two elements in the list is greater than the last element. Print a message based on the condition.

   1 2 3 4

   if numbers[0] + numbers[1] > numbers[-1]: print("Sum is greater") else: print("Sum is not greater")

6. Understanding Dictionary

   Drill: Create a dictionary where the keys are the numbers in the list, and the values are the squares of the numbers. Then, print the dictionary.

   1 2	number_dict = {number: number ** 2 for number in numbers} print(number_dict)

7. Return Statement

   Drill: Create a function that returns the sum of two numbers.

   1 2	def sum_numbers(num1, num2): return num1 + num2

8. Understanding Functions

   Drill: Using the function you just created, calculate the sum of the first and last numbers in the list.

   1 2	sum_result = sum_numbers(numbers[0], numbers[-1]) print(sum_result)

9. Understanding Classes

   Drill: Create a class “Calculator” with a method “add” that takes two numbers and returns their sum.

   1 2 3 4 5 6 7

   class Calculator: def add(self, num1, num2): return num1 + num2 # Usage calc = Calculator() sum_result = calc.add(numbers[0], numbers[-1]) print(sum_result)