The O(n) Club: Arithmetic Slices: Why Your Loops Are Weeping (And How to Fix Them)

The O(n) Club: Arithmetic Slices — Why Your Loops Are Weeping (And How to Fix Them)

⚡ TL;DR

Count all contiguous subarrays (length 3+) where the difference between each pair of numbers is constant. No, you don’t need three nested for-loops and a therapy budget. One pass, two counters—done:

// Brute force: send this to /r/ProgrammerHumor
int count = 0;
for (int i = 0; i < A.length - 2; i++) {
    for (int j = i + 2; j < A.length; j++) {
        boolean good = true;
        int diff = A[i+1] - A[i];
        for (int k = i+2; k <= j; k++) {
            if (A[k] - A[k-1] != diff) {
                good = false;
                break;
            }
        }
        if (good) count++;
    }
}

Meanwhile, you could try the real answer below and reclaim your night.

🧠 How Devs Usually Mess This Up

Let’s take a brief tour through the Minefield of Sad Dev Choices:

• Counting slices of length 2: Sorry, the party starts at 3. If you count pairs, you’ve invited the wrong guests.
• Assuming slices don’t overlap: Overlap is not just allowed, it’s the whole point. One number can party in lots of slices.
• Triple nested loops: Worked in 1993, but so did floppy disks. Also, interviewers will shorten your interview out of pity.

🔍 What’s Actually Going On

Picture a bored chef laying slices of bread for infinite sandwiches. If each slice lands with the same spacing—voilà, arithmetic! Every time you add a piece in the same rhythm, you’re making more sandwiches. Likewise, every time nums[i]-nums[i-1] == nums[i-1]-nums[i-2], your sequence earns fresh slices—all piggybacking off each other. So: keep a counter of streaks. More rhythm? More sandwiches (and code points).

🛠️ PseudoCode

• Set total = 0 (your sandwich tally), current = 0 (the number of ways to extend the last streak)
• Loop i from 2 to N-1:
  • If nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
  • current++ (the sandwich stack grows)
  • total += current (yum)
  • Else:
  • current = 0 (Chef lost the beat; start over)
• Return total

// Java in plain English
int total = 0;
int current = 0;
for (int i = 2; i < nums.length; i++) {
    if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
        current++;
        total += current;
    } else {
        current = 0;
    }
}
return total;

💻 The Code

public int numberOfArithmeticSlices(int[] nums) {
    int total = 0;
    int current = 0;
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
            current++;
            total += current;
        } else {
            current = 0;
        }
    }
    return total;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Arrays shorter than 3? Return 0—and maybe ask product why the input was empty.
• Negative numbers? Zeros? No curveballs—just difference checks.
• Forget slices overlap and you’ll undercount (and overdebug, probably at 3AM).
• Time: O(n). Space: O(1). Eyes: wide open. Resume: improved.

🧠 Interviewer Brain-Tattoo

Don’t grind through every possibility like a robot on low battery. Arithmetic slices reward the lazy: extend streaks as you go, and enjoy counting more with less code.