Home Week 1 | Grind 169 | Blind 75
Post
Cancel

Week 1 | Grind 169 | Blind 75

1. Two Sum

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> ump;
    int check, f(-1), s(-1);
    for(int i=0; i<nums.size(); i++){
      check = target - nums[i];
      if(ump.find(check) != ump.end()) {
          f = ump[check];
          s = i;
          break;
      }else ump[nums[i]] = i;
    }
    return {f, s};
}

2. Valid Parentheses

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

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

  • Practice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isValid(string s) {
    stack<char> st;
    for(char c : s){
        if(c == '('|| c == '{' || c == '['){
            st.push(c);
        }else{
            if(st.empty()) return false;
            if(c == ')' && st.top() != '(') return false;
            if(c == '}' && st.top() != '{') return false;
            if(c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
}

3. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

loading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head(0), tail = head;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;

        return head->next;
    }

4. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

1
2
3
4
5
6
7
8
int maxProfit(vector<int>& prices) {
    int buy = INT_MAX, profit = 0;
    for (auto price: prices){
        if(price < buy) buy = price;
        if(price - buy > profit) profit = price - buy;
    }
    return profit;
}

5. Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isPalindrome(string s) {
        string pal;

        if(!s.size()) return true;

        for(const auto &ch: s){
            if(isalnum(ch)){
                if(isupper(ch)) pal += ch+32;
                else pal += ch;
            }
        }

        int n = pal.size();

        for(int i=0; i<n/2; i++)
            if(pal[i] != pal[n-i-1])
                return false;


        return true;
}

6. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

loading

DFS

1
2
3
4
5
6
7
8
9
10
    TreeNode* invertTree(TreeNode* root) {

        if(!root) return NULL;

        TreeNode* tmp = invertTree(root->right);
        root->right = invertTree(root->left);
        root->left = tmp;

        return root;
    }

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            TreeNode* curr = st.top();
            st.pop();
            if (!curr) continue;
            st.push(curr->left);
            st.push(curr->right);
            swap(curr->left, curr->right);
        }
        return root;
    }

7. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isAnagram(string s, string t) {
    int hash[26] = {0};

    if(s.length() != t.length())
        return false;

    for(char ch:s)
        hash[ch-97]++;

    for(char ch:t)
        if(hash[ch-97])
            hash[ch-97]--;
        else
            return false;

    return true;
}

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

1
2
3
4
5
6
7
8
9
10
11
12
int search(vector<int>& nums, int target) {
    int mid, l = 0, r = nums.size() - 1;
    while(l<=r){
        mid = l + (r-l)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid] < target)
            l = mid+1;
        else
            r = mid-1;
    }
    return -1;
}

10. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

1
2
3
4
5
6
7
8
9
10
11
12
int maxSubArray(vector<int>& nums) {

    int maxi = INT_MIN, sum = 0, n = nums.size();

    for(const auto &e: nums){
        sum += e;
        maxi = max(maxi, sum);
        if(sum < 0) sum  = 0;
    }

    return maxi;
}

11. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
8
9
10
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

	if(p->val < root->val && q->val < root->val)
		return lowestCommonAncestor(root->left,p,q);

	if(p->val > root->val && q->val > root->val)
		return lowestCommonAncestor(root->right,p,q);

	return root;
}

12. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

1
2
3
4
5
6
7
8
9
10
int height(TreeNode* root) {
    if (!root) return 0;
    int left = height(root->left);
    int right = height(root->right);
    return (left == -1 || right == -1 || abs(left-right) > 1) ? -1 : max(left, right) + 1;
}

bool isBalanced(TreeNode* root) {
    return height(root) != -1;
}

13. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

1
2
3
4
5
6
7
8
9
10
11
bool hasCycle(ListNode *head) {

    ListNode *slow = head, *fast = head;

    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow) return true;
    }
    return false;
}

14. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

  • Practice

O(1) push

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyQueue {
public:
    stack<int> que;
    stack<int> tmp;
    int e;
    MyQueue() {
    }

    void push(int x) {

        while(!que.empty()){
            tmp.push(que.top());
            que.pop();
        }

        tmp.push(x);

        while(!tmp.empty()){
            que.push(tmp.top());
            tmp.pop();
        }
    }

    int pop() {
        e = que.top();
        que.pop();
        return e;
    }

    int peek() {
      return que.top();
    }

    bool empty() {
       return que.empty();
    }
};

O(1) push

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyQueue {
public:
    stack<int> que;
    stack<int> tmp;
    int front;
    MyQueue() {
    }

    void push(int x) {
        que.push(x);
    }

    int pop() {

        while(!que.empty()){
            tmp.push(que.top());
            que.pop();
        }

        front = tmp.top();
        tmp.pop();

        while(!tmp.empty()){
            que.push(tmp.top());
            tmp.pop();
        }
        return front;
    }

    int peek() {

        while(!que.empty()){
            tmp.push(que.top());
            que.pop();
        }

        front = tmp.top();

        while(!tmp.empty()){
            que.push(tmp.top());
            tmp.pop();
        }
        return front;
    }

    bool empty() {
       return que.empty();
    }
};

Amortized O(1) Push and Pop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class MyQueue {
public:
    stack<int> in;
    stack<int> out;
    int front;
    MyQueue() {
    }

    void push(int x) {
        in.push(x);
    }

    int pop() {

        if(out.empty()) {
        while(!in.empty()) {
            out.push(in.top());
            in.pop();
            }
        }

        front = out.top();
        out.pop();
        return val;
    }

    int peek() {

        if(out.empty()) {
            while(!in.empty()) {
                out.push(in.top());
                in.pop();
            }

        }

        return out.top();
    }

    bool empty() {
       return in.empty();
    }
};

15. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

1
2
3
4
5
6
7
8
9
10
11
    int firstBadVersion(int n) {
        int mid, l = 1, r = n;

        while(l<=r){
            mid = l + (r-l)/2;
            if(isBadVersion(mid) && !isBadVersion(mid-1)) return mid;
            if(isBadVersion(mid) == true) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
This post is licensed under CC BY 4.0 by the author.

Algorithm II | Study Plan | Leetcode

Week 2 | Grind 169 | Blind 75