The O(n) Club: Valid Triangle Number: Why Sticks Need Therapy (And Sorting)

The O(n) Club: Valid Triangle Number — Why Sticks Need Therapy (And Sorting)

⚡ TL;DR

Need to count just how many triangles you can make from random sticks? The brute-force approach: try every possible trio and pray your laptop doesn’t start whirring like a jet engine. Or, sort the array and use two pointers to count in O(N²) – because even geometry gets performance anxiety.

// Brute-force (not recommended for actual humans)
int count = 0;
for (int i = 0; i < n - 2; i++)
  for (int j = i + 1; j < n - 1; j++)
    for (int k = j + 1; k < n; k++)
      if (nums[i] + nums[j] > nums[k] &&
          nums[i] + nums[k] > nums[j] &&
          nums[j] + nums[k] > nums[i])
        count++;
// O(N³) — for when you don’t value your runtime or your sanity.

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Picture a frantic stick party. You want triangles — but the triangle inequality theorem is that annoying bouncer. For sides a, b, c: any two sides must sum to strictly more than the third. If not, you’re left with flat, sad, non-triangles that even computer graphics won’t render.

But — plot twist! Sort the array. Suddenly, testing a + b > c (with c as the largest) is enough. No need to sneak behind the math club and check every permutation. Just scan in style, two pointers at a time.

🛠️ PseudoCode

• Sort the sticks:
  

  Arrays.sort(nums);

  Sorting means your biggest stick is always last and your triangle checks get way easier.
• Loop over each possible biggest stick, backwards:
  

  for (int k = nums.length - 1; k >= 2; k--)

  The VIP of this triangle attempt is nums[k].
• Set up two pointers (i and j):

  int i = 0, j = k - 1; while (i < j)

  These dance from the start and end of the array up to k.
• If nums[i] + nums[j] > nums[k]: Bingo. Every combo between i and j works with this k (because it’s sorted). Tally them:

  count += j - i; j--;

• If not, your smallest stick is too scrawny — move it up:

  i++;

• Repeat until all (i, j, k) are checked. Return that glorious count.

💻 The Code

public int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int count = 0;
    int n = nums.length;
    for (int k = n - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negative or zero sticks? Not allowed at this party. Filter them out or risk math chaos.
• All sides equal? Yep, forms a triangle. Two sides too tiny? Sorry, not this time.
• Duplicates: Each unique group of three counts if it passes the triangle test — unless your interviewer has other plans.
• Time/space: Sorting: O(N log N). Two-pointer: O(N²). Brute force: Don’t.

🧠 Interviewer Brain-Tattoo

“If sorting makes your inequalities line up, you probably just halved your runtime. Sort first, panic later.”