Minimum Insertions to Balance Parentheses

Validating and repairing parenthesis strings requires tracking the relationship between opening and closing symbols. The algorithm monitors the current balance of unmatched left parentheses while counting necessary insertions.

As we traverse the string, left parentheses increment a balance counter, while right parentheses decrement it. When the balance becomes negative, it indicates an orphaned right parenthesis requiring a compensating left insertion. We reset the balance to zero and record this insertion. The final count includes both recorded insertions and any remaining positive balance representing needed right parentheses.

int minAdditions(char* s) {
    int balance = 0;
    int insertions = 0;
    
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            balance++;
        } else {
            balance--;
        }
        
        if (balance < 0) {
            insertions++;
            balance = 0;
        }
    }
    return insertions + balance;
}

Advanced Matching with 2:1 Parenthesis Ratio

When each left parenthesis must pair with exactly two right parentheses, the tracking mechanism adjusts to handle doubled requirements. The algorithm maintains a counter representing pending right parenthesis requirements.

Encountering a left parenthesis increases the pending count by two. If this results in an odd value, we insert a right parenthesis immediately to maintain even pairing, decrementing the pending count. When encountering a right parenthesis, we reduce the pending count. If no pending requirements exist (negative value), we insert a left parenthesis and set the pending count to one, indicating one more right parenthesis is needed to complete the new pair.

int minAdditionsDoubleRatio(char* s) {
    int pending = 0;
    int operations = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            pending += 2;
            if (pending % 2 == 1) {
                operations++;
                pending--;
            }
        } else {
            pending--;
            if (pending < 0) {
                operations++;
                pending = 1;
            }
        }
    }
    return operations + pending;
}

Next Greater Element with Monotonic Stacks

Finding the next greater element for each position in an array efficiently utilizes a monotonically decreasing stack. Processing elements from right to left, the stack maintains candidates for the "next greater" relationship.

For each element, we purge from the stack all values less than or equal to the current element, as they cannot serve as the next greater element for any preceding position. The surviving stack top (if any) represents the immediate next greater element; otherwise, we assign -1. The current element then enters the stack for subsequent evaluations.

int* nextGreaterElements(int* arr, int n, int* returnSize) {
    int* result = malloc(n * sizeof(int));
    int* dec_stack = malloc(n * sizeof(int));
    int top = -1;
    
    for (int i = n - 1; i >= 0; i--) {
        while (top >= 0 && dec_stack[top] <= arr[i]) {
            top--;
        }
        result[i] = (top >= 0) ? dec_stack[top] : -1;
        dec_stack[++top] = arr[i];
    }
    
    free(dec_stack);
    *returnSize = n;
    return result;
}

Smallest Lexicographical Subsequence with Unique Characters

To extract the lexicographically smallest subsequence containing each unique character exactly once, we combine greedy selection with monotonic stack behavior. The algorithm first records the final occurrence position of each character to determine future availability.

Using a stack to build the result, we skip characters already included. For each new character, we pop from the stack while the top element is lexicographically larger, and that element appears again later in the string (determined by comparing current index with stored last positions). This ensures smaller characters replace larger ones when possible, without sacrificing the ability to complete the full character set.

char* smallestSubsequence(char* text) {
    int last_pos[26] = {0};
    bool in_stack[26] = {false};
    char* buffer = malloc(strlen(text) + 1);
    int top = 0;
    
    for (int i = 0; text[i]; i++) {
        last_pos[text[i] - 'a'] = i;
    }
    
    for (int i = 0; text[i]; i++) {
        int curr = text[i] - 'a';
        if (in_stack[curr]) continue;
        
        while (top > 0 && text[i] < buffer[top-1] && 
               last_pos[buffer[top-1] - 'a'] > i) {
            in_stack[buffer[--top] - 'a'] = false;
        }
        
        buffer[top++] = text[i];
        in_stack[curr] = true;
    }
    
    buffer[top] = '\0';
    return realloc(buffer, top + 1);
}