Problem Description

You are given a list of people waiting in line, where each person has a specific weight, represented as an array weights. The bus has a maximum weight capacity, given by limit. People board the bus in the order they appear in the weights array, one by one.

Your task is to determine the index (0-based) of the last person who can successfully board the bus without exceeding the weight limit. If the next person in line would cause the total weight to exceed limit, they cannot board, and the process stops.

• Each person boards in order; you cannot skip or rearrange people.
• There is exactly one valid solution for each input.
• You must not reuse or skip elements.

For example, given weights = [100, 200, 150, 80] and limit = 400, the result should be 2 because the first three people (100 + 200 + 150 = 450) would exceed the limit, but only the first two (100 + 200 = 300) are under the limit, so the last person who can board is at index 1. (The example is for illustration; the actual logic will be clarified in the walkthrough.)

Thought Process

The problem is essentially about simulating a queue where people board a bus one after another, and we keep track of the running total of their weights. Once the running total would exceed the bus's weight limit by adding the next person, we stop and return the index of the last person who successfully boarded.

The brute-force way would be to try every possible combination of people, but since the boarding order is fixed and we cannot skip anyone, this simplifies the problem: we only need to add up weights in order and stop as soon as we reach or exceed the limit.

The optimization comes from realizing that a single pass through the array, maintaining a cumulative sum, is sufficient. There's no need for nested loops or backtracking, as the order is fixed and the process is deterministic.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize a cumulative sum: Start with a variable to keep track of the total weight so far, initialized to zero.
2. Iterate through the list: For each person's weight in the weights array, add it to the cumulative sum.
3. Check the limit: After adding each person's weight, check if the cumulative sum exceeds the limit.
   • If it does not exceed, continue to the next person.
   • If it does exceed, stop and return the index of the previous person (the last one who did not cause an overflow).
4. Edge case: If the total never exceeds the limit, return the index of the last person in the array.

This approach is efficient because it only requires a single pass through the input, and at each step, we do a simple addition and comparison.

Example Walkthrough

Let's use the following example:

• weights = [100, 200, 150, 80]
• limit = 400

Let's walk through each step:

1. Index 0: Add 100. Cumulative sum = 100. Still under limit.
2. Index 1: Add 200. Cumulative sum = 300. Still under limit.
3. Index 2: Add 150. Cumulative sum = 450. This exceeds the limit (400).
4. So, the last person to fit is at index 1 (the one before the overflow).

If all people fit (e.g., weights = [50, 50, 50] and limit = 200), then we would return index 2.

Time and Space Complexity

Brute-force approach: If we tried all possible combinations or permutations, it would be O(2^n), but since the order is fixed, this doesn't apply.

Optimized approach:

• Time Complexity: O(n), where n is the number of people in the weights array. We only make a single pass through the array.
• Space Complexity: O(1), since we only use a few variables for tracking the sum and index.

This efficiency is possible because we never need to store or revisit previous states—each decision depends only on the running total.

Code Implementation

def lastPersonToFit(weights, limit):
    total = 0
    for i, w in enumerate(weights):
        if total + w > limit:
            return i - 1
        total += w
    return len(weights) - 1
      

int lastPersonToFit(vector<int>& weights, int limit) {
    int total = 0;
    for (int i = 0; i < weights.size(); ++i) {
        if (total + weights[i] > limit) {
            return i - 1;
        }
        total += weights[i];
    }
    return weights.size() - 1;
}
      

public int lastPersonToFit(int[] weights, int limit) {
    int total = 0;
    for (int i = 0; i < weights.length; i++) {
        if (total + weights[i] > limit) {
            return i - 1;
        }
        total += weights[i];
    }
    return weights.length - 1;
}
      

function lastPersonToFit(weights, limit) {
    let total = 0;
    for (let i = 0; i < weights.length; i++) {
        if (total + weights[i] > limit) {
            return i - 1;
        }
        total += weights[i];
    }
    return weights.length - 1;
}
      

Summary

The key insight to this problem is that we only need to simulate the boarding process by maintaining a running sum of weights. As soon as adding the next person would exceed the bus's weight limit, we know the previous person was the last one to successfully board. This leads to a simple, efficient O(n) solution that is easy to implement and understand.

By focusing on the cumulative sum and stopping at the right moment, we avoid unnecessary complexity and deliver a solution that is both elegant and practical.