# A company is repainting its office – HackerRank Solution

## Problem

You can find the problem statement here.

## Explanation

Subarrays with a sum less than or equal to 7 are

Length 1 – , , , , , , [1 ]
Length 2 – [2, 3], [5, 1], [1, 1], [1, 2], [2, 1]
Length 3 – [5, 1, 1], [1, 1, 2], [1,2,1]
Length 4 – [1, 1, 2, 1]

[1, 1, 2, 1] is the largest subarray with a sum less than or equal to 7 and has a length of 4.

## Approach

The colors are arranged in a specific order so that each color complements the surrounding colors. Thus, we need to take consecutive elements only.

Our task can be simplified as finding the largest subarray of consecutive elements with a cost less than or equal to the budget.

We will be using the sliding window technique for solving this problem. We will start with the first element and continue adding the next elements until the cost is less than or equal to the budget. If the cost exceeds the budget, we shift the entire window to the right. Using this technique, we can calculate the cost for every consecutive subarray and get the maximum length.

## Algorithm

``````left = 0
right = 0
max_len = 0
cost = 0

while left < n
right = left
cost = 0
curr_len = 0
while right < n
cost += prices[right]
if cost <= money
curr_len += 1
right += 1

if curr_len > max_len
max_len = curr_len

left += 1

return max_len
``````

## Code

``````def max_paints(prices, money):
left = 0
right = 0
max_len = 0
cost = 0

while left < len(prices):
right = left
cost = 0
curr_len = 0
while right < len(prices):
cost += prices[right]
if cost <= money:
curr_len += 1
right += 1

max_len = max(max_len, curr_len)
left += 1

return max_len

prices = [2, 3, 5, 1, 1, 2, 1]
money = 7

print(max_paints(prices, money))``````

4

## Optimizing code

Instead of checking for all subarrays, we can stop checking for subarray whose length can never be greater than the current max length that we have. We now end the loop where the left pointer can not have a greater length than the current max length.

``````def max_paints(prices, money):
left = 0
right = 0
max_len = 0
cost = 0
n = len(prices)
while n - left >= max_len:
right = left
cost = 0
curr_len = 0
while right < n:
cost += prices[right]
if cost <= money:
curr_len += 1
right += 1

max_len = max(max_len, curr_len)
left += 1

return max_len

prices = [2, 3, 5, 1, 1, 2, 1]
money = 7

print(max_paints(prices, money))``````

## Output

4 