Number Problems: Set 1

• Greatest number of candies (LeetCode 1431)
• Increasing Triplet Sub-sequence (LeetCode 334)
• Product of Array Except Self (LeetCode 238)

Kids with greatest number of candies (LeetCode 1431)

You are given an array candies, where candies[i] is the number of candies the i-th kid has, and an integer extraCandies. You need to return a boolean array result, where result[i] is True if the i-th kid, after receiving all the extraCandies, will have the greatest number of candies among all the kids. Otherwise, result[i] should be False.

Note that it's possible for multiple kids to have the greatest number of candies.

Example:

• Input: candies = [2,3,5,1,3], extraCandies = 3

• Output: [true, true, true, false, true]

---

The Approach

1. Find the Maximum: First, determine the maximum number of candies any kid currently has. This value will be our benchmark.

2. Iterate and Compare: Go through the list of candies for each kid.

3. Check Condition: For each kid, add extraCandies to their current number of candies. If this new total is greater than or equal to the maximum found, they can have the greatest number of candies, so the result for them is True. Otherwise, it's False.

Using Python

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
    
        max_candies = max(candies)
        result = []
        
        for having in candies:
            if having + extraCandies >= max_candies:
                result.append(True)
            else:
                result.append(False)
                
        return result

Using a list comprehension:

class SolutionOneLiner:
    def kidsWithCandies(self, candies, extraCandies):
        max_candies = max(candies)
        return [candy + extraCandies >= max_candies for candy in candies]

In Java

import java.util.*;

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {

        int maxCandies = 0;
        for (int candy : candies) {
            if (candy > maxCandies) {
                maxCandies = candy;
            }
        }
        
        List<Boolean> result = new ArrayList<>();
        
        for (int candy : candies) {
            if (candy + extraCandies >= maxCandies) {
                result.add(true);
            } 
            else {
                result.add(false);
            }
        }
        
        return result;
    }
}

Increasing Triplet Subsequence (LeetCode 334)

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. Otherwise return false.

Input	Output	Explanation
[1,2,3,4,5]	true	Any ascending triplet works.
[5,4,3,2,1]	false	No ascending triplet exists.
[2,1,5,0,4,6]	true	Triplet (0,4,6) found.
[20,100,10,12,5,13]	true	Triplet (10,12,13) found.
[6,7,1,2]	false	Only descending pairs.
[5,1,6]	false	Not enough ascending elements.

---

Python Implementation (Optimal)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        
        if len(nums) < 3:
            return False

        first = float('inf')
        second = float('inf')

        for num in nums:
            if num <= first:    # Smallest so far
                first = num
            elif num <= second:  # Second Smallest
                second = num
            else:                # num > second & first
                return True
        return False

---

Java Implementation (Optimal)

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) return false;

        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= first) {
                first = num; // smallest so far
            } else if (num <= second) {
                second = num; // second smallest
            } else {
                // Found num > second > first
                return true;
            }
        }

        return false;
    }
}

---

Initialization Tricks

• float('inf') → positive infinity (initializing minimums).
• float('-inf') → negative infinity (initializing maximums).
• In Java → use Integer.MAX_VALUE and Integer.MIN_VALUE.

Algorithm (Greedy)

This is a classic example of a greedy linear scan.

We maintain two variables:

• first = smallest number seen so far.
• second = smallest number greater than first.

For each num:

1. If num <= first → update first. This keeps getting updated till a larger value is found.
2. Else if num <= second → update second.
3. Else → found num > second > first → return true.

If there was a number which was greater than first, second then it will trigger else so we can return true.

If the loop ends without finding such num, return false.

O(n) time and O(1) extra space.

---

Example nums = [2,1,5,0,4,6]:

• Start: first = inf, second = inf.
• num=2 → first=2.
• num=1 → first=1.
• num=5 → second=5.
• num=0 → first=0.
• num=4 → second=4.
• num=6 → 6>4>0 → return True. Triplet found.

Product of Array Except Self (LeetCode 238)

Given an integer array nums, return an array answer such that answer[i] is the product of all elements of nums except nums[i].

• The product of any prefix or suffix fits in a 32-bit integer.
• No division allowed
• should run in O(n) time

Input	Output
[1,2,3,4]	[24,12,8,6]
[-1,1,0,-3,3]	[0,0,9,0,0]

---

Approach 1: With Division (Easy but Not Allowed)

1. Compute total product of array and also find the Product (except zero)
2. If more than 2 zeroes, result is all zeroes
3. If one zero: only that index gets the product of all non-zero numbers.
4. If no zeros: answer[i] = total_product / nums[i]. (Works but violates problem’s “no division” constraint.)

def multiplefact(nlist):
    n = len(nlist)

    if n == 0:  # no elements
        return []

    result = [0] * n
    zeroes = 0
    product = 1
    zero_at = None

    # First pass: calculate product and count zeroes
    for i, num in enumerate(nlist):
        if num == 0:
            zeroes += 1
            zero_at = i
        else:
            product *= num

    # Case 1: more than one zero: all products are zero
    if zeroes > 1:
        return result

    # Case 2: exactly one zero: only zero position gets product
    elif zeroes == 1:
        result[zero_at] = product
        return result

    # Case 3: no zeros: divide product by each element
    for i in range(n):
        result[i] = product // nlist[i]  
        
    return result

Approach 2: Prefix and Suffix Products (Optimal)

For each index i:

• prefix[i] = product of all elements to left of i.
• suffix[i] = product of elements to right of i.
• result[i] = prefix[i] * suffix[i]. Multiplying prefix and suffix at each index gives product except self.

[1,   2,   3,  4,  5,  6]    Int list

[-,   1,   2,  6,  24, 120]   Prefixes
[720,360, 120, 30,  6,  -]    Sufixes

[720,360, 240, 180, 144, 120]  Result

We do this in two passes without extra prefix/suffix arrays if we’re clever.

---

Optimized Approach (No Extra Suffix Array)

We can do it in two passes with only the result array:

• Pass 1 (Left Products): store prefix products directly in result[i].

• Pass 2 (Right Products): maintain a running right product and multiply into result[i].

---

Python (Prefix & Suffix Arrays)

def productExceptSelf(nums):
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    result = [1] * n

    pre = 1
    for i in range(n):
        prefix[i] = pre
        pre *= nums[i]

    suf = 1
    for i in range(n-1, -1, -1):
        suffix[i] = suf
        suf *= nums[i]

    for i in range(n):
        result[i] = prefix[i] * suffix[i]

    return result

---

Python (Most Optimized – Single Result Array)

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # Prefix pass
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Suffix pass
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

O(n) time, O(1) extra space (excluding output array).

---

Java Version

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // Pass 1: store prefix products
        int left = 1;
        for (int i = 0; i < n; i++) {
            result[i] = left;
            left *= nums[i];
        }

        // Pass 2: multiply by suffix products
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }

        return result;
    }
}