How should I practice Shortest Subarray With a Target Remainder?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen and onsite interview problems in FastPrep.

Is Shortest Subarray With a Target Remainder associated with Google?

FastPrep tags this as a Google phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Shortest Subarray With a Target Remainder

Google● MediumINTERNPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given an integer array nums and a target remainder k. The modulus is the fixed constant 70001.

Return the length of the shortest nonempty contiguous subarray whose element sum has remainder k modulo 70001. Return -1 if no such subarray exists.

Values may be negative. Treat every remainder canonically in the range 0 through 70000.

Process the values from left to right using O(70001) auxiliary space rather than storing a prefix record for every array position.

Function

shortestSubarrayRemainder(nums: int[], k: int) → int

Examples

Example 1

nums = [2,3,1,2]k = 6return = 3

Both [2,3,1] and [3,1,2] have sum 6. No qualifying subarray has length 1 or 2, so the shortest length is 3.

Example 2

nums = [5,-2,4,-6,3]k = 2return = 2

The subarray [-2,4] has sum 2. No single value has remainder 2, so the answer is 2.

Example 3

nums = [70000,1,70001]k = 0return = 1

The one-element subarray [70001] has remainder 0, so no longer qualifying subarray can improve the answer.

Example 4

nums = [2,4,8]k = 7return = -1

No nonempty contiguous subarray has a sum congruent to 7 modulo 70001.

Constraints

1 <= nums.length <= 10^6.
-10^9 <= nums[i] <= 10^9.
0 <= k < 70001.
The answer must use a nonempty contiguous subarray.
Use O(nums.length) time and O(70001) auxiliary space.