D
DevExCode

LeetCode 611: Valid Triangle Number Solution

Master LeetCode problem 611 (Valid Triangle Number), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

611. Valid Triangle Number

Medium
ArrayTwo PointersBinary SearchGreedySorting

Problem Explanation

Explanation:

To solve this problem, we can sort the given array nums in non-decreasing order. Then, we can iterate through the array and for each element at index i, we fix it as the longest side of the potential triangle. We then use two pointers left and right to find the other two sides of the triangle. If the sum of the two sides is greater than the fixed side, we can form a valid triangle. We increment the count of valid triangles accordingly.

Algorithm:

  1. Sort the input array nums in non-decreasing order.
  2. Initialize a variable count to 0 to keep track of the number of valid triangles.
  3. Iterate over the array using a loop with index i from 2 to nums.length - 1.
    • Initialize two pointers left = 0 and right = i - 1.
    • While left < right, check if nums[left] + nums[right] > nums[i].
      • If true, increment the count by right - left because all elements between left and right can form a valid triangle with nums[i].
      • Decrement right to explore other potential triangles.
      • If false, increment left to increase the sum of the two sides.
  4. Return the final count as the result.

Time Complexity:

The time complexity of this algorithm is O(n^2) where n is the number of elements in the input array nums.

Space Complexity:

The space complexity of this algorithm is O(1) as we are not using any extra space other than a few variables.

:

Solution Code

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

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 611 (Valid Triangle Number)?

This page provides optimized solutions for LeetCode problem 611 (Valid Triangle Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 611 (Valid Triangle Number)?

The time complexity for LeetCode 611 (Valid Triangle Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 611 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 611 in Java, C++, or Python.

Back to LeetCode Solutions