▎976. Largest Perimeter Triangle

Difficulty: Easy

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

▎Example 1:

Input: 

nums = [2, 1, 2]

Output: 

5

Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

▎Example 2:

Input: 

nums = [1, 2, 1, 10]

Output: 

0

Explanation:

• You cannot use the side lengths 1, 1, and 2 to form a triangle.

• You cannot use the side lengths 1, 1, and 10 to form a triangle.

• You cannot use the side lengths 1, 2, and 10 to form a triangle.

As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

▎Approach

To solve this problem, we can follow these steps:

1. Sort the Array: Start by sorting the array in non-decreasing order.

2. Check Triplets: Iterate through the sorted array from the end to the beginning and check for valid triplets that can form a triangle using the Triangle Inequality Theorem.

3. Return the Perimeter: If a valid triplet is found, calculate and return their perimeter. If no valid triplet is found, return 0.

▎Implementation

Here’s a Python implementation of the approach:

def largestPerimeter(nums):
    # Sort the array in non-decreasing order
    nums.sort()
    
    # Iterate from the end of the sorted list to find a valid triangle
    for i in range(len(nums) - 1, 1, -1):
        # Check if nums[i-2], nums[i-1], nums[i] can form a triangle
        if nums[i - 2] + nums[i - 1] > nums[i]:
            # If they can, return their perimeter
            return nums[i - 2] + nums[i - 1] + nums[i]
    
    # If no valid triangle is found, return 0
    return 0

# Example usage:
print(largestPerimeter([2, 1, 2]))  # Output: 5
print(largestPerimeter([1, 2, 1, 10]))  # Output: 0

▎Conclusion

This solution efficiently finds the largest perimeter of a triangle that can be formed from three lengths in the given array. If no such triangle exists, it correctly returns 0.

Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation:
- From the first 3 customers, we collect three $5 bills.
- From the fourth customer, we collect a $10 bill and give back a $5.
- From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation:
- From the first two customers, we collect two $5 bills.
- For the next two customers, we collect a $10 bill and give back a $5 bill.
- For the last customer, we cannot give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

▎Constraints

• 1 ≤ bills.length ≤ 10⁵

• bills[i] is either 5, 10, or 20.

▎Solution Code

from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        c5 = 0  # Count of $5 bills
        c10 = 0 # Count of $10 bills
        
        for i in bills:
            if i == 5:
                c5 += 1
            elif i == 10:
                c10 += 1
                c5 -= 1
            else: # i == 20
                if c10 > 0:
                    c10 -= 1
                    c5 -= 1
                else:
                    c5 -= 3
            
            # Check if we have enough $5 bills to give change
            if c5 < 0:
                return False
        
        return True

Input: nums = [3, 9, 3]
Output: 2
Explanation:
- Operation 1: Replace 9 with [3, 6] → Array becomes [3, 3, 6, 3]
- Operation 2: Replace 6 with [3, 3] → Array becomes [3, 3, 3, 3, 3]
Thus, a total of 2 operations are required.

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation: 
The array is already in non-decreasing order. Therefore, no operations are needed.

▎Constraints

• 1 ≤ nums.length ≤ 10⁵

• 1 ≤ nums[i] ≤ 10⁹

▎Solution Code

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        operations = 0
        n = len(nums)
        
        # Start from the second last element and move backward
        for i in range(n - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                # Calculate how many parts we need to break nums[i] into
                parts = (nums[i] + nums[i + 1] - 1) // nums[i + 1]
                operations += parts - 1
                
                # Set nums[i] to the maximum value allowed
                nums[i] = nums[i] // parts
        
        return operations

def checkValidString(s: str) -> bool:
    low = high = 0  # low: min open count, high: max open count
    
    for char in s:
        if char == '(':
            low += 1
            high += 1
        elif char == ')':
            low = max(0, low - 1)  # Decrease open count but not below zero
            high -= 1
        else:  # '*'
            low = max(0, low - 1)  # Treat '*' as ')'
            high += 1  # Treat '*' as '('
        
        if high < 0:  # Too many ')', invalid
            return False
    
    return low == 0  # If low is zero, valid parentheses

# Test cases
print(checkValidString("()"))     # True
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True

▎Explanation

We keep track of the possible range of open parentheses using low and high:  

• low (minimum open count) decreases when ')' appears but never goes below 0.  

• high (maximum open count) increases when '(' or '*' (treated as '(') appears.  

• If high becomes negative at any point, the string is invalid.  

• Finally, if low == 0, the string is valid.  

🚀 Time Complexity: O(n)  
🔹 Space Complexity: O(1)

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0
        miss = 1
        i = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1
        return patches

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # Give every child 1 candy initially

        # Left-to-right pass: if a child has a higher rating than the left neighbor, give one more candy
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Right-to-left pass: if a child has a higher rating than the right neighbor, ensure they have more candy
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)