How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Implement longest subarray summing to k

Company: Google

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an integer array nums (length ≤ 200,000; values may be negative) and integer k, return the maximum length and the [l, r] indices of a contiguous subarray whose sum is exactly k. If multiple answers tie for length, choose the smallest l; if still tied, choose the smallest r. - First outline a correct O(n^2) brute‑force solution. - Then design an O(n) algorithm using prefix sums and a hash map. Prove correctness and explain how you ensure earliest indices under ties. - State time/space complexity and handle edge cases: k=0, all negatives, all zeros, duplicates, and empty or no‑solution cases.

Quick Answer: This question evaluates proficiency in array algorithms, prefix-sum reasoning, hash-based lookup patterns, and careful handling of edge cases and deterministic tie-breaking.

Given an integer array nums and an integer k, return [max_len, l, r], where nums[l:r+1] is a non-empty contiguous subarray whose sum is exactly k and max_len is its length. Tie-breaking: - If multiple valid subarrays have the same maximum length, choose the one with the smallest l. - If l is also tied, choose the one with the smallest r. If no such subarray exists, return [0, -1, -1]. Interview discussion expectations: 1) First outline a correct O(n^2) brute-force approach. A clean way is to build prefix sums so each subarray sum can be checked in O(1), then test all pairs (l, r) and keep the best answer under the tie rules. 2) Then implement an O(n) solution using prefix sums and a hash map. Why the O(n) idea works: a subarray l..r sums to k iff prefix[r] - prefix[l-1] = k, so for each r you need a previous prefix sum equal to prefix[r] - k. Storing the first index where each prefix sum appears gives the longest valid subarray ending at r. Scanning left to right and updating the best answer with the tie rules ensures the final answer has maximum length and the earliest valid indices among ties. Your implementation must handle negative numbers, zeros, duplicates, empty input, and no-solution cases.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i], k <= 10^9
nums may contain negative numbers, zeros, and duplicates
In languages with fixed-width integers, use 64-bit arithmetic for prefix sums

Examples

Input: ([1, -1, 5, -2, 3], 3)

Expected Output: [4, 0, 3]

Explanation: The subarray [1, -1, 5, -2] sums to 3 and has length 4, which is the longest.

Input: ([-2, -1, 2, 1], 1)

Expected Output: [2, 1, 2]

Explanation: The longest valid subarray is [-1, 2], from index 1 to 2.

Input: ([0, 0, 0, 0], 0)

Expected Output: [4, 0, 3]

Explanation: The entire array sums to 0, so the answer is the whole array.

Input: ([], 0)

Expected Output: [0, -1, -1]

Explanation: There is no non-empty subarray in an empty array.

Input: ([2, 3, -2, 4], 100)

Expected Output: [0, -1, -1]

Explanation: No contiguous subarray sums to 100.

Input: ([1, 2, 1, 2, 1], 3)

Expected Output: [2, 0, 1]

Explanation: Several subarrays have sum 3 and length 2, such as [1,2] and [2,1]. The tie is broken by choosing the smallest starting index, so [0, 1] is selected.

Input: ([-1, -1, -1, -1], -2)

Expected Output: [2, 0, 1]

Explanation: There are multiple length-2 subarrays summing to -2; choose the earliest one.

Input: ([5], 5)

Expected Output: [1, 0, 0]

Explanation: The single element itself forms the required subarray.

Solution

def solution(nums, k):
    first_index = {0: -1}
    prefix = 0
    best_len = 0
    best_l = -1
    best_r = -1

    for i, num in enumerate(nums):
        prefix += num
        need = prefix - k

        if need in first_index:
            start = first_index[need] + 1
            length = i - first_index[need]

            if (
                length > best_len
                or (
                    length == best_len
                    and (
                        best_l == -1
                        or start < best_l
                        or (start == best_l and i < best_r)
                    )
                )
            ):
                best_len = length
                best_l = start
                best_r = i

        if prefix not in first_index:
            first_index[prefix] = i

    return [best_len, best_l, best_r]

Time complexity: O(n). Space complexity: O(n).

Hints

A correct brute-force approach can be made O(n^2) by using prefix sums, so any subarray sum from l to r is prefix[r + 1] - prefix[l].
For the O(n) solution, store the first time each prefix sum appears. For index r, if prefix[r] - k was seen before at index j, then subarray (j + 1) to r sums to k.

Quick Overview

This question evaluates proficiency in array algorithms, prefix-sum reasoning, hash-based lookup patterns, and careful handling of edge cases and deterministic tie-breaking.