Minimum Removals to Stay within Budget

Problem Statement

Minimum Removals to Stay within Budget Problem Description Amazon developers are building a prototype feature that helps customers manage their cart within a given budget. You are given: An integer budget , the budget of the customer. An integer array cart_items of length n , where cart_items[j] is the price of the j -th item ( 0 -indexed). For each index i ( 0 <= i < n ), look at the sub-cart that contains the items from index 0 to index i (inclusive), that is cart_items[0..i] . For this sub-cart, find the minimum number of items that must be removed so that the total price of the items that remain does not exceed budget (a total equal to budget is allowed). The item at index i itself cannot be removed; only items at indices 0 to i - 1 may be removed. Each sub-cart is considered on its own: removals made for one index do not carry over to the next. Complete the function getMinRemovals(cart_items, budget) , which returns an array of length n whose value at index i is the minimum