SQL Intro

Quick practice exercises for learning SQL

What is SQL

A way to query data you have stored!

Two Pointers Application: One Pointer with Auxiliary State

We can use a single pointer to iterate linearly and have a second

344. Reverse String ::2:: - Easy

Topics: Two Pointers, String

Intro

Write a function that reverses a string.
The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.

Input	Output
s = ["h","e","l","l","o"]	["o","l","l","e","h"]
s = ["H","a","n","n","a","h"]	["h","a","n","n","a","H"]

Constraints:

1 ≤ s.length ≤ 10^5

s[i] is a printable ascii character

Abstraction

Given a string, reverse it

Pseudocode

Sol 2: Iterative In Place
1. (left, right = start, end)
2. while left < right:
    a. s[left], s[right] = s[right], s[left]
    b. left += 1 
    c. right -= 1
3. return

Test Cases

if __name__ == "__main__":

    sol = Solution()

    testCases = [

        # Regular strings
        "hello",
        "aaa",
        "abc",

        # Edge cases
        "",
        "a",

        # Palindrome patterns
        "racecar",
        "abba",
        "abca",
    ]

    for s in testCases:

        chars = list(s)
        sol.reverseString(chars)

        # !r calls repr() on the value before inserting it into the f-string,
        # for strings that means it wraps the output in quotes
        # w/ : 'hello' -> 'olleh'
        # w/o: hello -> hello
        print(f"{s!r} -> {''.join(chars)!r}")

Solution 1: [Two Pointer] Recursive In Place Reversal - Two Pointers/Opposite Ends

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        # Yes, this is a dumb way to do recursion, just a test for syntax

        def helper(left, right):
            if left >= right:
                return
            
            # Swap characters at the current ends
            s[left], s[right] = s[right], s[left]
            
            # Recurse inward
            helper(left+1, right-1)
        
        helper(0, len(s) - 1)

        # overall: tc O(n)
        # overall: sc O(n)

class Solution {
public:
    void reverseString(vector<char>& s) {

        // Two Pointer Approach (In-Place)

        // Substring Representation:
        //   - Maintain window [left, right] representing characters to swap
        //   - Goal: Swap characters until window meets in the middle

        // Idea:
        //   - Initialize two pointers at the ends of the array
        //   - Swap s[left] and s[right]
        //   - Move pointers inward
        //   - Stop when left >= right

        // Yes, this is a dumb way to do recursion, just a test for syntax

        helper(s, 0, s.size() - 1);

        // overall: tc O(n)
        // overall: sc O(n)
    }

private:
    void helper(vector<char>& s, int left, int right) {
        if (left >= right) {
            return;
        }

        // Swap characters at the current ends
        swap(s[left], s[right]);

        // Recurse inward
        helper(s, left + 1, right - 1);
    }
};

Solution 2: [Two Pointer] Iterative In Place Reversal - Two Pointers/Opposite Ends

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        left = 0
        right = len(s) - 1

        # tc: iterate over half the array O(n)
        while left < right:

            # Swap characters at left and right
            s[left], s[right] = s[right], s[left]

            # Shrink window from both ends
            left += 1
            right -= 1
         
        # overall: tc O(n)
        # overall: sc O(1)

class Solution {
public:
    void reverseString(vector<char>& s) {

        // Two Pointer Approach (In-Place)

        // Substring Representation:
        //   - Maintain window [left, right] representing characters to swap
        //   - Goal: Swap characters until window meets in the middle

        // Idea:
        //   - Initialize two pointers at the ends of the array
        //   - Swap s[left] and s[right]
        //   - Move pointers inward
        //   - Stop when left >= right

        int left = 0;
        int right = s.size() - 1;

        // tc: iterate over half the array O(n)
        while (left < right) {

            // Swap characters at left and right
            swap(s[left], s[right]);

            // Shrink window from both ends
            left++;
            right--;
        }

        // overall: tc O(n)
        // overall: sc O(1)
    }
};

LeetCode: SQL