Very excited to share a solution I came up with for a "hard" tiered interview question from Exponent, which is one of the resources I am using to prepare for technical interviews.

Here is the problem given:

• Determine if a given array contains a subarray of at least two elements whose sum is a multiple of a specified number k.
• An array is considered to have a "good subarray" if there exists at least one subarray (consisting of two or more elements) such that the sum of the elements in this subarray is a multiple of k.
• For example, the array [23, 2, 4, 7] with k = 6 has a "good subarray" ([2, 4]), as the sum 6 is a multiple of k = 6. The array [5, 0, 0, 0] with k = 3 does not have any "good subarray", as no subarray of two or more elements sums to a multiple of 3.

Immediately, I recognized this problem needed to use the Sliding Window technique due to its specification of needing to determine a sum amount from a subarray and having a specified number to base our sum on. Ideally, we want to have an O(N) solution. I will show the pseudo code I wrote for this problem, followed by the edge cases and issues I experienced when testing my solution, and finally the final solution I came up with.

As always, I would love to hear about any optimizations or improvements to my solution, but I was very proud to figure this out on my own.

Initial Pseudo Code

1. // initialize a startWindow to 0 and currentSum to 0
2. // Create for loop with an endWindow initialize to 0, iterating over the nums array
3. // Do something to work towards meeting the condition
4. // Check if the condition is met, if so return true
5. // If answer is not found in the for loop, shrink the window to check if other subarrays satisfy the requirements (do with while loop)
6. // After shrinking the window (we are inside while loop), check if the subarray meets the condition. If not then increment the startWindow var and continue the loop 
7. // If the while loop does not return true, then return false

Why Do We Need Two Loops?

The reason why I decided to use two loops is because it is possible for us to find the correct answer in the first iteration of the nums array. For example, nums[0] and nums[1] could already meet the condition. Or perhaps nums[0] nums[1] and nums[2] meets the condition. Eventually, as we increase the size of our subarray, we would like to return as early as possible with the correct answer. However, only increasing the window size does not guarantee we looked for every combination of possible subarray sums. Just because the first three values of the array did not meet the condition, or even if the first four did not either, that does not mean that the last three did not meet the condition. If we stopped after only increasing the window, then we would never be able to tell if the other subarrays that exists could meet the condition. Therefore, we need another loop to shrink the window after we check the for loop.

How is the solution O(N) when two loops are used?

The time complexity remains linear because the loops are not nested. When the function runs, we are at most iterating over the nums array one time on each invocation of the function. This is how we are able to remain in a linear time complexity while using two loops.

How do we know if currentSum meets the condition?

Firstly, we will ensure we update current sum by either adding the new value we see to it before comparing (for loop) or by subtracting the first value of the subarray before shrinking the window (incrementing startWindow in the while loop). Now the actual comparison logic I came up with was figuring out if the currentSum is divisible by k. If the result of currentSum / k is a whole number, then we know the condition is met. The easiest way to do this is to use the modulus operator to check if a remainder exists.

currentNum % k === 0

However, that is not the only logic needed to determine if we meet the criteria. If currentSum is ever zero, then we would get a false positive since 0 % k would always return zero. So, I added an additional check to ensure that would not affect our answer either.

currentNum > 0 && currentNum % k === 0

Now I finally covered ALL my bases to pass every test 😎... or so I thought until only 4/6 tests passed 🤨. Then I realized I forgot to think about a couple of edge cases.

Edge Cases & Issues

Here are the issues I ran into with my initial plan:

• Issue #1: If null was put in place of an array or if the array was empty, then I would get an error and fail the test.
• Solution #1: Add a check if nums is null or has a length of 0 and return false if that is the case.

• Issue #2: If nums is an array of negative numbers, then checking if currentNums has a remainder of zero when using the modulus operator would not suffice (console would log -0 if -18 % 3 was the check).
• Solution #2: Use Math.abs() to ensure the modulus result was a positive number and the currentSum being larger than one was recognized for negative numbers as well.

My Code:

Thank you for getting this far and understanding my thought process behind this problem. Without any further ado, here is my solution in code.

function hasGoodSubarray(nums, k) {


  let startWindow = 0, currentSum = 0


  if(nums === null || !nums.length)return false
  
  
      for(let endWindow = 0; endWindow < nums.length;endWindow++){
          // do something
          currentSum += nums[endWindow]
          // check if done
          if(Math.abs(currentSum) > 1 && Math.abs(currentSum % k) === 0) return true
      }
  
      // shrink window if answer is not found on for loop pass
      while(startWindow < nums.length){
          currentSum -= nums[startWindow];

          if(currentSum > 0 && currentSum % k === 0) return true

          startWindow++
      }
      return false
  }
  
  
  // debug your code below
  console.log(hasGoodSubarray([23, 2, 4, 7], 6));
  console.log(hasGoodSubarray([-3, -1, -2, -5, -7], 3));
  console.log(hasGoodSubarray(null, 3));

Let me know if you found another way to solve this problem. I hope you enjoyed reading about my solution, I am very proud to continue to make progress and have the ability to answer more and more difficult questions. I take pride in earning my solutions, which is why I am so excited not only to share my solution, but continue to build on the concrete understanding of the problem by explaining my thought processes. Feel free to message me on linkedin or email me at cassius.reynolds.dev@gmail.com.

Thank you and happy coding!