Maximum Size Subarray Sum Equals k

Asked atAmazonVisa
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

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 here

javascript

/**
 * @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+
  1. 01Maintain the running prefix sum.
  2. 02Store the first index for every prefix value.
  3. 03For sum s, look for s-k.
  4. 04Use the earliest stored index to maximize length.
  5. 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.

Get 5x interviews10 free auto-applies. No card.
  • 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

Or practice this question first

Next question