Ian Soan's LeetCode Solutions

website·Indexed 30 days ago

https://iansoan.pages.dev

A collection of C++ solutions for various LeetCode problems, including detailed time and space complexity analysis (T and S) for each implementation.

Tokens: 104.2K
Snippets: 342
Records: 373
Agent score: 75%

What's inside Ian Soan LeetCode Solutions

Determine if a string is a subsequence of another
A string s is considered a subsequence of string t if s can be formed by deleting zero or more characters from t without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde", but "aec" is not.
Constraints:
- s.length is between 0 and 100.
- t.length is between 0 and 10,000.
- Both strings consist only of lowercase English letters.
```
// Example 1
// Input: s = "abc", t = "ahbgdc"
// Output: true

// Example 2
// Input: s = "axc", t = "ahbgdc"
// Output: false
```
https://iansoan.pages.dev/leetcode-392/

Replace words in a sentence with the shortest root using a Trie

To replace derivatives in a sentence with their shortest root from a dictionary, use a Trie (prefix tree) to store all roots. For each word in the sentence, traverse the Trie to find the shortest prefix that is marked as a valid root. If a match is found, replace the word with that root; otherwise, keep the original word. This approach ensures that if multiple roots match, the shortest one is selected.

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord = false;
    TrieNode() {
        for(int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for(auto c : word) {
            if(!node->child[c - 'a']) {
                node->child[c - 'a'] = new TrieNode();
            }
            node = node->child[c - 'a'];
        }
        node->isWord = true;
    }

    string searchShortestRoot(string word) {
        TrieNode* node = root;
        string prefix = "";
        for (char c : word) {
            if (!node->child[c - 'a']) break;
            prefix.push_back(c);
            node = node->child[c - 'a'];
            if (node->isWord) return prefix;
        }
        return word;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        stringstream ss(sentence);
        Trie t;
        for(auto word : dictionary) {
            t.insert(word);
        }
        string token;
        string res;
        while (getline(ss, token, ' ')) {
            res += t.searchShortestRoot(token) + " ";
        }
        res.pop_back();
        return res;
    }
};

Calculate average customer waiting time for a single-chef restaurant

To calculate the average waiting time for customers, track the chef's availability and the cumulative wait time. For each customer, the order starts at either their arrival time or when the chef finishes the previous order (whichever is later). The waiting time for an individual customer is the difference between when their order is completed and when they arrived. The final result is the total waiting time divided by the number of customers.

#define ll long long

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers)
    {
        int n = customers.size();
        int endTime = 0;
        ll waitTime = 0;
        for (int i = 0; i < n; ++i)
        {
            // Chef starts at max of arrival time or previous end time
            endTime = max(customers[i][0], endTime) + customers[i][1];
            // Wait time is completion time minus arrival time
            waitTime += endTime - customers[i][0];
        }
        return (double)waitTime / n;
    }
};

Implement a string-to-integer (atoi) conversion function

The myAtoi function converts a string to a 32-bit signed integer by following these steps:

Whitespace: Ignore all leading whitespace characters (' ').
Signedness: Check if the next character is '-' or '+'. If neither is present, assume the number is positive.
Conversion: Read digits until a non-digit character is encountered or the end of the string is reached. Leading zeros are ignored. If no digits are read, the result is 0.
Rounding: Clamp the result to the 32-bit signed integer range: [-2^31, 2^31 - 1]. Values less than -2,147,483,648 are rounded to -2,147,483,648; values greater than 2,147,483,647 are rounded to 2,147,483,647.

Constraints:

String length: 0 <= s.length <= 200
Allowed characters: English letters, digits, spaces, '+', '-', and '.'.

class Solution {
public:
    int myAtoi(string s) {
        int sign = 1;
        int res = 0;
        int i = 0;
        int n = s.size();

        // 1. Skip leading whitespace
        while (i < n && s[i] == ' ') i++;

        // 2. Determine sign
        if (i < n && s[i] == '+') {
            sign = 1;
            i++;
        } else if (i < n && s[i] == '-') {
            sign = -1;
            i++;
        }

        // 3. Convert digits and handle overflow
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0';
            
            // Check for 32-bit signed integer overflow
            if ((res > INT_MAX / 10) || (res == INT_MAX / 10 && digit > INT_MAX % 10)) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            
            res = 10 * res + digit;
            i++;
        }
        return sign * res;
    }
};

Determine if two strings are isomorphic

Two strings s and t are considered isomorphic if the characters in s can be replaced to get t while preserving the order of characters. Each character must map to exactly one other character (or itself), and no two characters may map to the same character.

Constraints:

1 <= s.length <= 5 * 10^4
t.length == s.length
Strings consist of any valid ASCII character.

class Solution {
public:
    bool isIsomorphic(string s, string t)
    {
        // Maps to store the last seen position (1-indexed) of characters in s and t
        unordered_map<char, int> m1;
        unordered_map<char, int> m2;

        int n = t.size();

        for (int i = 0; i < n; i++)
        {
            // If the positions of the current characters in s and t don't match,
            // they are not mapping consistently.
            if (m1[s[i]] != m2[t[i]])
            {
                return false;
            }
            // Update the last seen position to i + 1 (to distinguish from default 0)
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

Rotate a singly-linked list to the right by k places

To rotate a linked list to the right by k places, the most efficient approach is to connect the tail of the list to the head to form a circular loop, then break the loop at the appropriate position.

Key steps include:

Handle base cases (empty list or single node).
Calculate the length of the list n to handle cases where k is larger than the list length using k = k % n.
Connect the last node to the head to create a circle.
Find the new tail, which is located at position n - k - 1 from the start.
Set the new head to new_tail->next and break the circle by setting new_tail->next = nullptr.

Complexity:

Time Complexity: O(N), where N is the number of nodes in the list.
Space Complexity: O(1).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // base case
        if (!head || !head->next) return head;

        // Calculate linked list length
        ListNode* cur = head;
        int n = 1;
        while(cur->next) {
            cur = cur->next;
            ++n;
        }

        // Connect tail to head to form a circle
        cur->next = head;

        // Handle cases where k > n
        k %= n;

        // Find the new tail: it is at position n - k - 1
        ListNode* new_tail = head;
        for (int i = 0; i < n - k - 1; ++i) {
            new_tail = new_tail->next;
        }

        // The new head is the node after the new tail
        ListNode* new_head = new_tail->next;

        // Break the circle
        new_tail->next = nullptr;
        
        return new_head;
    }
};

Determine if cards can be rearranged into consecutive groups (LeetCode 846)

To determine if a hand of cards can be rearranged into groups of size groupSize where each group consists of consecutive cards, you can use a frequency map (TreeMap in C++) to keep track of card counts. The strategy is to always start a group with the smallest available card and check if the subsequent groupSize - 1 consecutive cards are available in the map. If any card in the sequence is missing, the cards cannot be rearranged as required.

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        int n = hand.size();
        // If total cards aren't divisible by groupSize, it's impossible
        if(n % groupSize) return false;

        // Use a map to store frequencies; keys are sorted automatically in C++ std::map
        map<int, int> freq;
        for(auto h : hand) ++freq[h];

        while(!freq.empty()) {
            // Start with the smallest available card
            int first = freq.begin()->first;

            // Try to form a group of groupSize consecutive cards
            for(int i = first; i < first + groupSize; ++i){
                // If a required consecutive card is missing, return false
                if(!freq.count(i)) {
                    return false;
                }

                // Decrease frequency and remove the key if it reaches 0
                --freq[i];
                if(freq[i] == 0) {
                    freq.erase(i);
                }
            }
        }
        return true;
    }
};

Count alternating color groups in a circular array

To count alternating groups of length k in a circular array of colors, extend the array by appending the first k-1 elements to the end. This transforms the circular problem into a linear one. Iterate through the extended array, maintaining a counter for the current alternating sequence length. If the current element differs from the previous one, increment the counter; otherwise, reset it to 1. Whenever the counter reaches k, a valid alternating group is found.

Time Complexity: O(N + K - 1) Space Complexity: O(N + K)

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k)
    {
        // Extend the array to handle circularity
        for (int i = 0; i < k - 1; ++i)
        {
            colors.push_back(colors[i]);
        }

        int res = 0;
        int cnt = 1; // Tracks the length of the current alternating group

        for (int i = 1; i < colors.size(); ++i)
        {
            // Check if the current tile color is different from the previous one
            if (colors[i] != colors[i - 1])
            {
                ++cnt;
            }
            else
            {
                cnt = 1; // Reset if colors are the same
            }
            
            // If the alternating sequence reaches length k, count it as a group
            if (cnt >= k) ++res;
        }
        return res;
    }
};

Solve the Filter Installation Strategy problem

The goal is to replace all '?' characters in a string $S$ (consisting of 'a', 'b', and '?') with either 'a' or 'b' such that no three identical characters appear consecutively (e.g., no 'aaa' or 'bbb').

Constraints:

String length $N$ is between 1 and 500,000.
It is guaranteed that a valid solution always exists.

Example Transformations:

"a?bb" $ ightarrow$ "aabb"
"??abb" $ ightarrow$ "ababb", "bbabb", or "baabb"
"a?b?aa" $ ightarrow$ "aabbaa"
"aa??aa" $ ightarrow$ "aabbaa"

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string solution(string &S)
{
    vector<int> seen;

    // Map 'a' to 1, 'b' to -1, and '?' to 0 for easier arithmetic checks
    for (char c : S)
    {
        if (c == 'a') seen.push_back(1);
        else if (c == 'b') seen.push_back(-1);
        else seen.push_back(0);
    }

    // Pad boundaries to avoid out-of-bounds access during neighbor checks
    seen.insert(seen.begin(), {0, 0});
    seen.insert(seen.end(), {0, 0});

    int n = seen.size();

    auto helper = [&seen](int i)
    {
        if (seen[i] == 0)
        {
            // Check if placing a specific character would create a triplet
            // by checking sums of neighbors
            vector<int> sums = {seen[i - 2] + seen[i - 1], seen[i - 1] + seen[i + 1], seen[i + 1] + seen[i + 2]};
            if (find(sums.begin(), sums.end(), 2) != sums.end())
            {
                 seen[i] = -1; // Must be 'b' to avoid 'aaa'
            } else if (find(sums.begin(), sums.end(), -2) != sums.end())
            {
                seen[i] = 1; // Must be 'a' to avoid 'bbb'
            }
        }
    };

    // Pass 1: Left to right to resolve forced placements
    for (int i = 2; i < n - 2; ++i) helper(i);

    // Pass 2: Right to left to resolve forced placements
    for (int i = n - 3; i > 1; --i) helper(i);

    // Pass 3: Final pass to fill remaining '?' based on the previous character
    for (int i = 2; i < n - 2; ++i) {
        if (seen[i] == 0)
        {
            seen[i] = (seen[i - 1] > 0) ? -1 : 1;
        }
    }

    string res;
    for (int i = 2; i < n - 2; ++i)
    {
        if (seen[i] == 1) res += 'a';
        else if (seen[i] == -1) res += 'b';
    }

    return res;
}

Find the minimum moves to make a string not a palindrome

Given a string S of length N, the goal is to find the minimum number of characters to remove from either the left or right end so that the remaining string is not a palindrome. An empty string is not considered a palindrome.

Logic for the minimum moves:

If the string is already not a palindrome, 0 moves are required.
If the string is a palindrome but contains at least two different characters, removing one character from either end will result in a string that is not a palindrome (1 move).
If the string is a palindrome and all characters are identical (e.g., "xxxx"), the only way to make it not a palindrome is to remove all characters until the string is empty (N moves).

#include<vector>
#include<string>

using namespace std;

int solution(string &S)
{
    int n = S.size();
    int left = 0, right = n - 1;
    bool isPalindrome = true;

    // Check if the string is a palindrome
    while (left < right)
    {
        if (S[left] != S[right])
        {
            isPalindrome = false;
            break;
        }
        ++left; --right;
    }

    // Case 1: Already not a palindrome
    if (!isPalindrome) return 0;

    // Case 2: Check if all characters are the same
    bool isSame = true;
    for (int i = 1; i < n; ++i)
    {
        if (S[i] != S[0])
        {
            isSame = false; 
            break;
        }
    }

    // Case 3: All characters are identical, must remove all N characters
    if (isSame) return n;

    // Case 4: Palindrome with different characters, removing one end breaks it
    return 1;
}

Reorder a singly linked list in-place

To reorder a singly linked list from the form L0 → L1 → … → Ln-1 → Ln to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … without modifying node values, follow these steps:

Find the middle: Use a slow and fast pointer approach. When the fast pointer reaches the end, the slow pointer will be at the middle.
Reverse the second half: Reverse the linked list starting from the node after the middle pointer.
Interleave the halves: Merge the first half and the reversed second half by alternating nodes from each.

Complexity:

Time Complexity: O(N)
Space Complexity: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        // 1. Find the middle node
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 2. Reverse the second half
        ListNode* cur = slow->next;
        ListNode* prev = nullptr;
        while(cur) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        // Disconnect the first half from the second half
        slow->next = nullptr;

        // 3. Interleave the two halves
        ListNode *first = head;
        ListNode *second = prev;
        while(second) {
            ListNode* node1 = first->next;
            ListNode* node2 = second->next;
            first->next = second;
            second->next = node1;
            first = node1;
            second = node2;
        }
    }
};

Solve the Snakes and Ladders problem (LeetCode 909)
The goal is to find the minimum number of moves to reach square n² on an n x n board. The board is labeled in Boustrophedon style (zigzag), starting from the bottom-left (board[n-1][0]) and alternating directions each row.
Movement Rules:
1. From current square curr, roll a 6-sided die to choose a destination next in the range [curr + 1, min(curr + 6, n²)].
2. If board[r][c] at the destination is not -1, you must move to the value specified by the snake or ladder.
3. You only follow a snake or ladder once per move; if the destination of a ladder is another ladder, you do not follow the second one.
4. The game ends when you reach square n².
Return the least number of moves required, or -1 if the end is unreachable.
```
// Example Input
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
// Output: 4
```
https://iansoan.pages.dev/leetcode-909/