Bounded Range Segment Calculator 2 — Problem Statement & Solution Guide

Dynamic ProgrammingEasyKnapsack State Optimization

TimeO(N*C)

SpaceO(C)

Problem Description

You are tasked with optimizing resource allocation within a fixed capacity constraint. Given an array of integers representing the weight of distinct items and a target capacity, determine the maximum total value that can be accumulated without exceeding the capacity limit. Each item can be selected at most once. This problem models a classic 0/1 Knapsack scenario where the goal is to maximize the sum of selected elements subject to a strict upper bound on their total weight.

The input consists of an array weights where each element represents the cost or size of an item, and an integer capacity representing the maximum allowable total weight. You must return the maximum possible sum of weights that can be packed into the knapsack such that the sum does not exceed capacity. If no items can be selected, return 0.

This problem requires a dynamic programming approach to efficiently compute the optimal subset sum. The state transition involves deciding whether to include the current item or skip it, updating the maximum achievable sum for each possible capacity level up to the given limit.

DSA Pattern Breakdown

"Bounded Range Segment Calculator 2"

easy

WHY DOES IT MATTER?

0/1 knapsack embodies the bounded subset‑sum pattern, a cornerstone for resource allocation, budgeting, and capacity planning problems. Mastery of this pattern equips engineers to tackle a wide range of optimization tasks where choices are exclusive and resources are limited.

OPTIMIZATION CHALLENGE

The key insight is recognizing that each DP state only depends on the previous row, enabling a one‑dimensional DP that iterates capacities backward. This reduces memory from O(N·C) to O(C) and often improves cache performance, making the solution viable for large capacities.

REAL-WORLD CONNECTION

Think of a cloud provider allocating virtual machines to a fixed physical host: each VM consumes CPU/memory (weight) and brings revenue (value). The provider must pack VMs to maximize revenue without exceeding host capacity, mirroring the knapsack constraints.

During an interview, write the 2‑D recurrence first, then immediately discuss space compression. Interviewers love seeing you think about both time and space, and mentioning the reverse‑iteration trick signals deep DP understanding.

COMPLEXITY AT A GLANCE

⏱ Time:O(N*C)

💾 Space:O(C)

Core Theory — Why This Approach?

The Bounded Range Segment Calculator 2 is a classic 0/1 knapsack problem where each item can be taken at most once. The naive solution enumerates every subset of items, leading to exponential time O(2^N), which quickly becomes infeasible even for moderate N. Dynamic programming leverages the optimal substructure: the best value achievable with the first i items and capacity w depends only on the decisions for the i‑th item and the optimal solution for the remaining capacity. By building a DP table dp[i][w] that stores the maximum value using the first i items within weight w, we transform the exponential search into a pseudo‑polynomial algorithm with time O(N·C) where C is the capacity.

The DP recurrence is: dp[i][w] = max(dp[i‑1][w], dp[i‑1][w‑weight[i]] + value[i]) if weight[i] ≤ w, otherwise dp[i][w] = dp[i‑1][w]. This captures the choice of either skipping or taking the current item. To further improve space, we can compress the table to a one‑dimensional array iterating capacities in reverse, because each state only depends on the previous row. This reduces space from O(N·C) to O(C) while preserving correctness. The approach scales to typical interview constraints (N ≤ 10^3, C ≤ 10^5) and demonstrates the power of DP in converting combinatorial explosion into tractable computation.

Interview Questions on This Problem

Q1How would you modify the DP solution if each item could be taken unlimited times (unbounded knapsack) instead of at most once?

Switch to a forward iteration over capacities: for each item, iterate w from weight[i] to C and update dp[w] = max(dp[w], dp[w‑weight[i]] + value[i]). This allows reuse of the same item because the current dp[w] can incorporate the same item multiple times.

Q2Can you achieve O(N·√C) time for this problem using a different technique?

Yes, by applying a meet‑in‑the‑middle approach: split the items into two halves, enumerate all subset sums for each half (O(2^{N/2})), sort one list, and for each sum in the other list binary‑search the best complementary sum ≤ C. This yields O(2^{N/2}) time, which is sub‑exponential but not O(N·√C); however, for small N it can be faster than DP when C is huge.

Q3What changes are needed if the problem asks for the exact capacity usage rather than "≤ capacity"?

Initialize dp array with -∞ (or a sentinel) except dp[0] = 0, and after filling the table, the answer is dp[C] if it is not -∞; otherwise, no exact fill exists. The recurrence stays the same, but you must avoid treating unreachable states as zero.

Examples

Example 1

Input

weights = [2, 3, 5, 7], capacity = 10

Output

Explanation: We evaluate subsets of the array [2, 3, 5, 7] to find the maximum sum <= 10. Possible combinations: 2+3+5=10, 2+7=9, 3+7=10, 5+7=12 (exceeds). The maximum valid sum is 10, achieved by selecting items with weights 2, 3, and 5, or 3 and 7.

Example 2

Input

weights = [1, 2, 3, 4, 5], capacity = 6

Output

Explanation: We seek the maximum subset sum <= 6. Combinations: 1+2+3=6, 1+5=6, 2+4=6, 1+2+4=7 (exceeds). The maximum valid sum is 6, achievable by multiple subsets such as {1,2,3} or {1,5}.

Example 3

Input

weights = [10, 20, 30], capacity = 25

Output

Explanation: We check subsets of [10, 20, 30] with sum <= 25. Options: 10, 20, 10+20=30 (exceeds), 30 (exceeds). The maximum valid sum is 20, achieved by selecting the item with weight 20.

Example 4

Input

weights = [1, 1, 1, 1], capacity = 3

Output

Explanation: All items have weight 1. We can select up to 3 items to stay within the capacity of 3. The sum of any 3 items is 3, which is the maximum possible without exceeding the limit.

Constraints

1 <= weights.length <= 1000
1 <= weights[i] <= 1000
1 <= capacity <= 100000
The sum of weights[i] may exceed capacity, but individual weights are positive integers.

Optimal Approach & Strategy

Use dynamic programming with a 1‑D array of size capacity+1, updating it in reverse order for each item to capture the 0/1 choice, achieving O(N·C) time and O(C) space.

Brute Force Approach

Enumerate all subsets of items and compute total weight and value for each, keeping the best that stays within capacity. This runs in O(2^N) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N*C)

function solution(nums, max_val, start, end) {
   let n = nums.length;
   let dp = new Array(n + 1).fill(0).map(() => new Array(max_val + 1).fill(0));
   for (let i = start; i <= end; i++) {
       for (let j = 0; j <= max_val; j++) {
           if (i === 0) {
               dp[i][j] = nums[i];
           } else {
               dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
           }
       }
   }
   return Math.max(...dp[end]);
}

class Solution {
   public:
       int solution(vector<int>& nums, int max_val, int start, int end) {
           int n = nums.size();
           vector<vector<int>> dp(n + 1, vector<int>(max_val + 1, 0));
           for (int i = start; i <= end; i++) {
               for (int j = 0; j <= max_val; j++) {
                   if (i == 0) {
                       dp[i][j] = nums[i];
                   } else {
                       dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                   }
               }
           }
           return *max_element(dp[end].begin(), dp[end].end());
       }
   };

class Solution {
   public int solution(int[] nums, int max_val, int start, int end) {
       int n = nums.length;
       int[][] dp = new int[n + 1][max_val + 1];
       for (int i = start; i <= end; i++) {
           for (int j = 0; j <= max_val; j++) {
               if (i == 0) {
                   dp[i][j] = nums[i];
               } else {
                   dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
               }
           }
       }
       return Math.max(dp[end][max_val], 0);
   }
}

def solution(nums, max_val, start, end):
   n = len(nums)
   dp = [[0] * (max_val + 1) for _ in range(n + 1)]
   for i in range(start, end + 1):
       for j in range(max_val + 1):
           if i == 0:
               dp[i][j] = nums[i]
           else:
               dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
   return max(dp[end])

function solution(nums, max_val, start, end) {
   let n = nums.length;
   let dp = new Array(n + 1).fill(0).map(() => new Array(max_val + 1).fill(0));
   for (let i = start; i <= end; i++) {
       for (let j = 0; j <= max_val; j++) {
           if (i === 0) {
               dp[i][j] = nums[i];
           } else {
               dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
           }
       }
   }
   return Math.max(...dp[end]);
}

Asked in Top Tech Interviews

SwiggyInfosys

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Bounded Range Segment Calculator 2 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Dynamic Programming

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Bounded Range Segment Calculator 2 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor