Maximum Size Subarray Sum Equals k
The problem
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.
Input: nums = [1,-1,5,-2,3], k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
Input: nums = [-2,-1,2,1], k = 1 Output: 2 Explanation: The subarray [-1, 2] sums to 1 and is the longest.
Input: nums = [1,-5,1,5,1], k = 1
- 1 <= nums.length <= 2 * 105
- -104 <= nums[i] <= 104
- -109 <= k <= 109
cpp
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
// Your code goes herer
}
};java
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
// Your code goes here
}
}python
class Solution(object):
def maxSubArrayLen(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# Your code goes herejavascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxSubArrayLen = function(nums, k) {
// Your code goes here
};csharp
public class Solution
{
public int MaxSubArrayLen(int[] nums, int k)
{
// Your code goes here
}
}go
func maxSubArrayLen(nums []int, k int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Maintain the running prefix sum.
- 02Store the first index for every prefix value.
- 03For sum s, look for s-k.
- 04Use the earliest stored index to maximize length.
- 05Seed prefix zero at index minus one.
Reference answer
Then expect these follow-ups
How would you count all target-sum subarrays?
Tests: frequency maps
How do you return the actual boundaries?
Tests: index tracking
Hiring now
Visa has 638 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Software Engineer Intern
GB - London, United Kingdom
Sr. Software Engineer (3+ yrs, DevOps, Cloud, Coding, Infra)
IN - Bengaluru, India
Sr Software Engineer (3-5 yrs of exp - Full stack development, Java, React, Gen AI)
IN - Bengaluru, India
Next question