The O(n) Club: Running Sum of 1D Array – Because If You Can’t Count, You Can’t Code

The O(n) Club: Running Sum of 1D Array – Because If You Can’t Count, You Can’t Code

⚡ TL;DR

Add up each number as you go; every slot gets the sum up to that point. If you somehow make this O(n²), consider a nap.

// Brute-force (sleepy version):
int[] runningSum(int[] nums) {
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = 0; j <= i; j++) sum += nums[j];
        result[i] = sum;
    }
    return result;
}

🧠 How Devs Usually Mess This Up

Common rookie mistakes:

• Nesting loops for no reason – Welcome to O(n²) purgatory.
• Ditching the current number – Forget to add nums[i], your sums will make no sense.
• Piling onto the array – Appending to a new array instead of updating by index. Spoiler: wrong length.
• Off-by-one madness – Indexing is not jazz; you can’t improvise in Java.
• Panic at negatives – Negative, zero, million, pizza—doesn’t matter. Addition always works.

🔍 What’s Actually Going On

Imagine keeping a tip jar and jotting the total after every drop. That’s the running sum. You need to march through the array once, carrying the running tally like a responsible barista (but with less caffeine and more focus on indexing correctly).

Want speed? Reuse the same array (if you don’t mind mutating it) or build a new one for your “functional programming” street cred. Either way, keep it O(n).

🛠️ PseudoCode

• Grab a result array, or use the original if you’re bold.
• Set sum = 0.
• Walk the array:
  • Add nums[i] to sum.
  • Write sum at result[i] (or overwrite input if you love side effects).

// Java sample
int[] runningSum(int[] nums) {
    int[] res = new int[nums.length];
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        res[i] = sum;
    }
    return res;
}

• For “in-place”:

  for (int i = 1; i < nums.length; i++) {
      nums[i] += nums[i - 1];
  }

💻 The Code

// New array version
public int[] runningSum(int[] nums) {
    int[] res = new int[nums.length];
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        res[i] = sum;
    }
    return res;
}
 // Mutate input (demo only if nobody else needs nums!)
public int[] runningSumInPlace(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Single element? No problem, it’s itself.
• Zeroes or negatives? Absolutely fine. It’s addition, not a mood ring.
• Don’t mutate arrays if you’ll need the original—copy first if you even suspect someone cares!
• Time: O(n). (Use that in interviews. Trust me.)
  Space: O(1) if in-place, O(n) if you’re careful and kind to input.

🧠 Interviewer Brain-Tattoo

“If you make running sum hard, wait until you meet prefix sum. Just add, Chandler.”