Adding Ones

Problem Overview

The array starts as n zeros, and each update k adds 1 to every position from k to the end.

Intuition

The array starts as n zeros, and each update k adds 1 to every position from k to the end. Applying every update directly could touch almost the whole array each time. Instead, each update only records where its range starts. The final value at a position is the number of updates whose start is at or before it, which is a prefix sum of those marks. Because that running count can only grow, neighboring positions often share the same value, and the same boxed number can be reused for all of them.

Algorithm

1Create a count array of size n. For each update k, increment index k - 1.
2Presize the result list to n.
3Walk the positions from left to right, adding each mark to a running count.
4When the count changes, box the new value once. Append the current boxed value at every position.
5Return the list.

Example Walkthrough

Input: n = 4, updates = [1,1,2,3]

1. The marks are 2 at index 0, 1 at index 1, and 1 at index 2.
2. The running count becomes 2, then 3, then 4.
3. The last position adds nothing new and keeps 4.

Output: [2, 3, 4, 4]

Common Pitfalls

• Updates are 1 based, so update k marks index k - 1.
• Adding 1 to every position for every update takes n times q time and is too slow for large inputs.
• The range always runs to the end of the array, so no end marker is needed.
• Boxed Integer values above 127 are new objects each time, so reusing one for a run of equal counts saves allocations.

Adding Ones.java

Java

// Approach: An update k adds 1 to every position from k to n, so mark a +1
// at index k - 1 in a count array. The value at each position is then the
// prefix sum of those marks. The prefix sums never decrease, so a run of
// equal values reuses one boxed Integer instead of boxing every element.
// Time: O(n + q) Space: O(n), where q is the update count.

import java.util.ArrayList;

class Solution {

    public ArrayList<Integer> update(int n, int[] updates) {
        int[] mark = new int[n];
        for (int k : updates) {
            mark[k - 1]++;
        }

        ArrayList<Integer> result = new ArrayList<>(n);
        int running = 0;
        Integer boxed = 0;
        for (int i = 0; i < n; i++) {
            if (mark[i] != 0) {
                running += mark[i];
                boxed = running;
            }
            result.add(boxed);
        }
        return result;
    }
}

Was this solution helpful?