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.

```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.

### 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 = {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; } ```

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(); } }; ```

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 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; } ```