You can find the problem statement here.
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.
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.
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
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))
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))
- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
- HackerRank Day 12 Solution in Python: Inheritance