PS – LeetCode – Quinsh's Programming Record

1071. Greatest Common Divisor of Strings – Solution

Difficulty: Easy
Topics: Math, String

For two strings s and t, we say “t divides s” if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

I initially solved this like this:

string gcdOfStrings(string str1, string str2) {
        int minlen = min(str1.size(), str2.size());
        // check if one is substring of another. if not, return "".
        if (str1.substr(0, minlen) != str2.substr(0, minlen)) {
                return "";
        }
        for (int i = minlen; i > 0; i--) {
            // if str1 and str2 are not divisible by i, pass
            if (! (str1.size() % i == 0 && str2.size() % i == 0)) {
                continue;
            }
            // check if GCD is correct
            string GCD = str1.substr(0, i);
            for (int j = 0; j < str1.size(); j+=i) {
                if (GCD != str1.substr(j, i)) goto pass;
            }
            for (int j = 0; j < str2.size(); j+=i) {
                if (GCD != str2.substr(j, i)) goto pass;
            }
            return GCD;
            pass: ;
        }
        return "";
    }

But there was a simpler logic:

str1 and str2 have a gcd iff str1+str2 == str2+str1

Proof:
str1 = m (GCD)
str2 = n (GCD)
str1 + str2 = (m + n) GCD = str2 + st1

if they have a gcd, find it with math -> gcd().

string gcdOfStrings(string str1, string str2) {
        return (str1 + str2 == str2 + str1) ? 
        str1.substr(0, gcd(size(str1),size(str2))) : "";
    }

3. Longest Substring Without Repeating Characters – Solution

Difficulty: medium
Topics: Hash Table, String, Sliding Window

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution

It’s easy to come up with a O(n^2) approach. Just check the length of longest substring starting from 0 to end.

O(n) approach needs more thinking:

int lengthOfLongestSubstring(string s) {
        
        map<char, int> charMap;
        int start = -1;
        int maxLen = 0;
        
        for (int i = 0; i < s.size(); i++) {
            if (charMap.count(s[i]) != 0) {
                start = max(start, charMap[s[i]]);
            }
            charMap[s[i]] = i;
            maxLen = max(maxLen, i-start);
        }
        
        return maxLen;
    }

This puts the index of where characters appears in a hashmap. So as we iterate from 0 to end, we can know where that character appeared last time and find the length. Each time we recalculate the max.

Reflection

interesting concept to blackbox:

whenever finding a maximum value through iteration, let’s use maxval = max(maxval, newval)
use hashmap to store the value and its frequency, or value and index.
If the value is a character or linear sequence number, it can be stored in an array as well. But using hashmap can be more efficient space-wise.

1. Two Sum – Solution

Difficulty: Easy
Topics: Array, Hash Table

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:Input: nums = [3,3], target = 6 Output: [0,1]

Solution

While storing the numbers in hashmap, check if the complementary (target – number) is in the hashmap.

Note that hashmap[nums[i]] = i; should not be before the part where we search for comp. This is because search for comp should be done in values previously put in, not including the current value.

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++){
            int comp = target - nums[i];
            if (hashmap.count(comp) > 0){
                res = {hashmap[comp], i};
                return res;
            }
            hashmap[nums[i]] = i;
        }
        return res;
    }

658. Find K Closest Elements – Solution

Question

Difficulty: medium
Topics: Array, Two Pointers, Binary Search, Sliding Window

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example 1:Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]

Example 2:Input: arr = [1,2,3,4,5], k = 4, x = -1 Output: [1,2,3,4]

Solution

This was a question that I struggled a lot. It was harder than usual binary search problems. There are many ways to think for this problem.

Solution 1: O(N⋅log(N)+k⋅log(k))

compute the distances between the elements and x, sort it and display the first k elements. When displaying it, sort again.

Solution 2: O(log(N)+k) – Bin. Search + 2 Pointers

Search the index of element closest to x. Then, start l and r pointers from there and expand them based on the smallest distance.

Solution 3: O(log(N−k)) – Find the left bound.

Search the left bound with binary search. Let l = 0 and r = N-k which is the maximum index that a left bound can be.

compute the mid point. Now, assuming the mid is the left bound, mid+k is the right bound. Then,

If value at mid is closer to x:

mid and further cannot be the left bound because then the right bound would be more distant from x than mid.

But, since there can be an even better left bound in the left side, we continue the bin search with the left side.

so we do r = mid;

If value at mid+k is closer to x:

index at mid or lower can’t be left bound. The left bound is somewhere between mid+1 ~ mid+k

so we do l = mid+1;

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = arr.size() - k;
        while (l < r){
            int mid = (l+r)/2;
            if (x - arr[mid] > arr[mid+k] - x){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return vector<int>(arr.begin() + l, arr.begin() + l + k);
    }
};

There is another way of seeing this: (from lee215’s solution post)

We compare the distance between x - A[mid] and A[mid + k] - x
If we assume A[mid] ~ A[mid + k] is sliding window

case 1: x – A[mid] < A[mid + k] – x, need to move window go left
——-x—-A[mid]—————–A[mid + k]———-

case 2: x – A[mid] < A[mid + k] – x, need to move window go left again
——-A[mid]—-x—————–A[mid + k]———-

case 3: x – A[mid] > A[mid + k] – x, need to move window go right
——-A[mid]——————x—A[mid + k]———-

case 4: x – A[mid] > A[mid + k] – x, need to move window go right
——-A[mid]———————A[mid + k]—-x——

Reflection

I think whenever using binary search, I should think about based on what criteria I will choose the left side or the right side given a mid point. This was particularly harder because I didn’t think of finding the left bound. Let’s remember that when finding a range, I can try to find only left or right bound.

50. Pow(x,n) – Solution

Difficulty: medium
Topics: math, recursion

Implement pow(x, n), which calculates x raised to the power n

Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000

Solution

O(n) approach would be just multiplying x n times:

$Pow(x,n)=x*x*x\dotsm \Large$

O(logn) approach is using an algorithm called “binary exponentiation“. This requires understanding that x^n can be decomposed in 2 ways:

if n is even:

$x^{n} = {x}^{\frac{n}{2}}*{x}^{\frac{n}{2}} \Large$

if n is odd:

$x^{n} = x * x^{n-1} = x * {x}^{\frac{n-1}{2}} * {x}^{\frac{n-1}{2}} \Large$

This can be handled recursively. x^n is decomposed into expressions with smaller ‘n’s until n becomes 0. When n becomes 0, we return 1.

class Solution {
public:
    double binaryExp(double x, long long n) {
        if (n == 0) return 1;
       
        // Handle case where, n < 0.
        if (n < 0) return 1.0 / binaryExp(x, -1 * n);
       
        // Perform Binary Exponentiation.
        double rec = binaryExp(x, n / 2);
        if (n % 2 == 1) return x * rec * rec;
        else return rec * rec;
    }

    double myPow(double x, int n) {
        return binaryExp(x, (long long) n);
    }
};

34. Find First and Last Position of Element in Sorted Array – Solution

Difficulty: medium
Topics: array, binary search

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Leetcode problem 34

Solution

The way to handle this is by finding start and end pos separately.

We can do this by implementing separate binary searches to find lower bound and higher bound of target.

OR just make one binary search to find the lower bound of target and find the end position by finding the lower bound of (target+1).

The first approach is shown below:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // if it's empty,
        if (nums.size() == 0){
            vector<int> res = {-1, -1};
            return res;
        }
        
        // search left bound
        int l = 0, r = nums.size()-1;
        int leftrange = 0;
        while (l < r){
            int mid = (l+r)/2;
            if (nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        if (nums[l] != target) leftrange = -1; 
        else leftrange = l; 

        // search right bound
        l = 0, r = nums.size()-1;
        int rightrange = 0;
        while (l < r){
            int mid = (l+r+1)/2;
            if (nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        if (nums[l] != target) rightrange = -1;
        else rightrange = l; 
        
        // print the result
        vector<int> res = {leftrange, rightrange};
        return res;
    }
};

By only implementing binSearch that finds lower bound:

class Solution {
private:
    int lower_bound(vector<int>& nums, int low, int high, int target){
        while(low <= high){
            int mid = (low + high) >> 1;
            if(nums[mid] < target){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        int startingPosition = lower_bound(nums, low, high, target);
        int endingPosition = lower_bound(nums, low, high, target + 1) - 1;
        if(startingPosition < nums.size() && nums[startingPosition] == target){
            return {startingPosition, endingPosition};
        }
        return {-1, -1};
    }
};

Since we already have a built in lower_bound library function, we can use that:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int startingPosition = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int endingPosition = lower_bound(nums.begin(), nums.end(), target+1) - nums.begin() - 1;
        if(startingPosition < nums.size() && nums[startingPosition] == target){
            return {startingPosition, endingPosition};
        }
        return {-1, -1};
    }
};