Tag: typescript

Posted on by

LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Solution is a greedy recursion. Iterate in reverse order to make sure to get the largest solution first. 


function constructDistancedSequence(n: number): number[] {
    const size = 2 * n - 1;
    const result: number[] = new Array(size).fill(0);
    const used: boolean[] = new Array(n + 1).fill(false);
    function backtrack(index: number): boolean {
        if (index === size) return true; // If we filled the array, return success
        if (result[index] !== 0) return backtrack(index + 1); // Skip filled positions
        for (let num = n; num >= 1; num--) { // Try from largest to smallest
            if (used[num]) continue;
            if (num === 1) {
                // Place 1 (only once)
                result[index] = 1;
                used[1] = true;
                if (backtrack(index + 1)) return true;
                used[1] = false;
                result[index] = 0;
            } else {
                // Place num at index and index + num (if valid)
                if (index + num < size && result[index + num] === 0) {
                    result[index] = result[index + num] = num;
                    used[num] = true;
                    if (backtrack(index + 1)) return true;
                    used[num] = false;
                    result[index] = result[index + num] = 0;
                }
            }
        }
        return false;
    }
    backtrack(0);
    return result;
}
Posted on by

LeetCode 20 Valid Parentheses in Typescript

The mental challenge one might experience here is that JavaScript doesn’t have abstract data structures like stacks and queues built into the language. Implementations of those structures use an array underneath. So solving this problem is just as easy in TypeScript as it is in C++ with a stack. The problem is defined as:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1: Input: s = “()” Output: true

Example 2: Input: s = “()[]{}” Output: true

Example 3: Input: s = “(]” Output: false

Example 4: Input: s = “([])” Output: true

Solution:

function isValid(s: string): boolean {
    
    const st:string[] = [];
    for( const c of s){
        
        if( c === '(' || c === '[' || c === '{'){
            st.push(c);
        } else {
            const last =  st[st.length - 1];
            if( c === '(' && last === ')') st.pop();
            else if( c === '[' && last === ']') st.pop();
            else if( c === '{' && last === '}') st.pop();
            else st.push(c);
        }

        
    }
    
    return st.length === 0;
};