DAY 75 OF 90 · Two markers

Longest under budget

Medium90 Days of Looping

Inputs

values is a list of 0 to 14 whole numbers, each from 1 to 9. budget is a whole number from 0 to 40.

Your tasks

Keep a left marker at 0, a running sum of 0 and best of 0.
Use a loop where right moves along values, adding each number to sum. While sum is more than budget, take values[left] away from sum and move left right.
After fixing the window, update best with its length right - left + 1.
Complete longestUnderBudget so it returns best. Return it, do not print it.

Example

With values = [3, 1, 2, 4, 1, 1] and budget = 6, longestUnderBudget returns 3.

Rules

A stretch is neighbouring numbers.
If even a single number is more than the budget, the stretch is empty.

Test data

TEST DATA 1: values is [3, 1, 2, 4, 1, 1], budget is 6

TEST DATA 2: values is [], budget is 5

Practice focus

Two pointers and sliding windows: loops that move two positions instead of one. Two pointers and sliding windows turn many quadratic answers into linear ones.

Day 74 Day 76 All 90 days