Algorithms: Max Length of the Subarray Where the Sum of Elements is Less than or Equal to K

Here’s a recent coding challenge that I completed for a job interview. Recent as in… I finished it about 30 minutes ago… I had a devil of a time figuring out what to call this problem, but basically…

You’re given an array and an integer k. Return the length of the longest subarray where when you add up the elements inside the subarray, it’s less than or equal to k.

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

Output:  2

# So, just to clarify here… All of the possible subarrays in the above example would be:

[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

[1, 2] is the largest subarray where the sum is less than or equal to 3. [1, 2].length = 2, so we return 2.

OKAY THEN.

I’ve been learning about creating recursive functions with the help of helper methods, or helper lambdas in Ruby’s case. For this code challenge I felt like I didn’t have time to play around with new techniques so I just created two separate methods.

find_subarrays takes an array and spits out the combination of subarrays. I called [1..-1] because I didn’t want to include the empty array that is included in the beginning.

My max_length function takes in an array and the integer k, creates a holder variable qualified_subarrays_lengths. Originally I was going to throw the entire subarrays into the variable when I found a match, but then I decided that just the length would be enough to solve the problem.

First I found all the subarrays by calling find_subarrays. Then I iterated over this array and checked to see if the sum of elements were equal to or below k (*oh look it’s our good friend Inject, thanks for being helpful!). If so I pushed the length of the subarray onto the qualified_subarrays_lengths array. After iterating across all subarrays, I just took the max value from qualified_subarrays_lengths.

TA DA.

Leave a Reply

Your email address will not be published.

Scroll To Top