LeetCode Daily Problem P611: Number of Valid Triangles

---

Timeline

Timeline

2025-09-26

init

Multiple loop optimization

---

Problem:

P611 Number of valid triangles

https://leetcode.cn/problems/valid-triangle-number/description/?envType=daily-question&envId=2025-09-26

The standard approach for this problem is to first fix the largest side, then use two pointers—one moving from front to back (representing the smallest side), and one moving from back to front (representing the second largest side). If the sum of the value pointed to by the front pointer and the value pointed to by the back pointer satisfies the triangle condition, then the smallest side can be any value between the two pointers, and then we can make the second largest side smaller to see if it still satisfies. If it does not satisfy, it means the smallest side is too small, so make the smallest side larger. Since it is the smallest side, its value cannot be greater than the second largest side. When the two pointers meet, it means we have finished traversing all cases where the largest side is the currently fixed largest side. At this point, make the largest side smaller, and then restart the traversal with the smallest side and the second largest side.

#include <algorithm>
#include <vector>

using std::vector;

class Solution {
public:
  // Given an array nums containing non-negative integers, return the number of triplets that can form the three sides of a triangle.
  // 1 <= nums.length <= 1000
  // 0 <= nums[i] <= 1000
  int triangleNumber(vector<int> &nums) {
    // The sum of any two sides of a triangle is greater than the third side.

    if (nums.size() < 3) {
      return 0;
    }
    vector<int> vec(nums);
    int n;
    int i, j, k;
    int res = 0;

    // Sort
    std::sort(nums.begin(), nums.end());
    // Deduplicate; sorting is required before deduplication.
    // vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

    n = vec.size();
    // First fix the largest side. k is the largest side in the triangle, j is the next, and i is the smallest.
    for (k = n - 1; k >= 2; k--) {
      i = 0;
      j = k - 1;
      while (i < j) {
        if (nums[i] + nums[j] > nums[k]) {
          // Because j traverses from k-1 toward the front, and i traverses from 0 toward the back.
          // So if nums[i] + nums[j] > nums[k]
          // Then all [i, j-1] can form a triangle with j and k.
          res += (j - i);
          --j;
        } else {
          // If the triangle condition is not satisfied, it means i is too small.
          // Increment i, and exit the loop when i == j.
          // Because at this point k and j are fixed, and no i can satisfy the triangle condition.
          // It means k is too large, so decrement k.
          i++;
        }
      }
    }
    return res;
  }
};