# Interesting Problems

[Array-String](#array-string)
[Linked-List](#linked-list)
[Stacks-Queues](#stacks-queues)
[Trees](#trees)
[Recursion](#recursion)
[All](#all)

# Array-String
[Duplicate Zeros](https://leetcode.com/explore/featured/card/fun-with-arrays/525/inserting-items-into-an-array/3245)
input: [1,0,2,3,0,4,5,0]
output: [1,0,0,2,3,0,0,4]

a duplicate array, where the zeros are copied twice and the others only once. The length should be same as the input array and operation should be done in-place.

>solution:
We can improve it to O(N) time and O(1) space.
Basically, we apply two pointers.
i is the position in the original array,
j is the position in the new array.
(the original and the new are actually the same array.)
The first we pass forward and count the zeros.
The second we pass backward and assign the value from original input to the new array.
so that the original value won't be overridden too early.

[Find All Numbers Disappeared in an Array](https://leetcode.com/explore/featured/card/fun-with-arrays/523/conclusion/3270/)
given an array of size n with elements 1 ≤ a[i] ≤ n, return an array of the missing values.
runtime O(n), no extra space.
Input: [4,3,2,7,8,2,3,1]
Output:[5,6]

>solution:
First iteration to negate values at position whose equal to values appear in array. Second iteration to collect all position whose value is positive, which are the missing values

[Find if two strings are one error distance away](https://www.lintcode.com/problem/one-edit-distance/description)
input: “pan”, “pane”
output: true
input: “paan”, “pan”
output: true
input: “pain”, “pane”
output: false
>solution:
There are two types of error distance - replacement and insertion/deletion. If the two strings are of same length, check for replacement, else for the other one.

# Linked-List
[is there a cycle in linked list](https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212/)
>solution:
two pointers: one slow, one fast. The slow one goes through every node and the faster one skips every one along the way. If they meet, it has cycle.

[Linked List Cycle II](https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1214/)
find out where the cycle (if any) begins
>solution:
(floyd’s cycle finding algorithm) send two pointers - fast and slow, see if they meets at some point M. If they do, send a pointer from M and another from the head. They’ll meet at the point where the cycle begins.

[Remove Nth Node From End of List](https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/)
Given linked list: 1->2->3->4->5, and n = 2
After removing the second node from the end, the linked list becomes 1->2->3->5
>Solution:
To do this in one pass, set free a pointer and get to the (n+1) th node. Then start another pointer from the head and resume the other. While the fast one gets to the end, the slow one should be at the position just before the node to be deleted.

# Stacks-Queues
[Perfect Squares](https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1371/)
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
in: 12 out: 3
in: 13 out: 2
>Solution:
BFS. Maintain a queue and keep pushing (n - i*i) and return the zero’s step flag.

[Daily Temperatures](https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1363/)
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.

input: [73, 74, 75, 71, 69, 72, 76, 73]
output: [1, 1, 4, 2, 1, 1, 0, 0]

>Solution:
Traverse from the end. Maintain a Stack where gradually larger digits are pushed. The smaller are popped. How many are popped should be counted. The main idea is: if a number T1 is larger than another T2 in the stack, we no longer need T2 to check, our condition will be satisfied at T1.

[Binary Tree Inorder Traversal](https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1383/)
Input: [1,null,2,3]

1
 \
  2
 /
3

Output: [1,3,2]
>Solution:
Push all the lefts of the current node to a stack. after pushing, get the value of the stack’s top, pop it, set the current node to the right of it.

[Implementing Queue Using Stack](https://leetcode.com/explore/learn/card/queue-stack/239/conclusion/1386/)
>Solution:
Take two stacks. In one, keep pushing. Use the other for peeking and popping. No need to pop clean the second after every peek. So the ammortized time complexity here is O(1).

[Convert Sorted Array to BST](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)
>Solution:
Recursively, get the middle element and make it the root of the left and right subtrees.

# Trees
[Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
check if the tree is BST or not
>Solution:
run an in-order traversal.

[Course Schedule](https://leetcode.com/problems/course-schedule/)
Some courses have prerequisites. Is there a way to complete them all?
>Solution:
sort topologically.

[Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)
>Solution:
Go deeper, if found a match of one of the two nodes, return it, else return null. If not-null values are got from left and right subtrees, the current root is the LCA.

[Unique BST](https://leetcode.com/problems/unique-binary-search-trees/)
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
>Solution:
DP procedure: To build a tree contains {1,2,3,4,5}. First we pick 1 as root, for the left sub tree, there are none; for the right sub tree, we need count how many possible trees are there constructed from {2,3,4,5}, apparently it's the same number as {1,2,3,4}. So the total number of trees under "1" picked as root is dp[0] * dp[4] = 14. (assume dp[0] =1). Similarly, root 2 has dp[1]*dp[3] = 5 trees. root 3 has dp[2]*dp[2] = 4, root 4 has dp[3]*dp[1]= 5 and root 5 has dp[0]*dp[4] = 14. Finally sum the up and it's done.

[Same Tree](https://leetcode.com/problems/same-tree/)
Are the two trees s and t exactly same?
>Solution:
To see if two trees are identical, run a recursion and walking parrallelly with the left and right nodes.

[Subtree of another tree](https://leetcode.com/problems/subtree-of-another-tree/submissions/)
Is the tree t a subtree of s?
>Solution:
With each step, see if the trees are identical. If it isn’t, go left and right and see if they are identical.

# Recursion
[Reverse Linked List](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/2378/)
>Solution:
Go to the end till null, return the new head pointer. Set the next of the old head to null.
initial:
1 -> 2 -> 3 -> 4 -> 5
after reverseList(2):

1 -> 2 <- 3 <- 4 <- 5
     |
     v
    null

>after operate on 1:
null <- 1 <- 2 <- 3 <- 4 <- 5

[Searching in a BST](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/3233/)
given a BST and a value, find and return the subtree whose root’s value matches with the given one.
Given the tree:

    4
   / \
  2   7
 / \
1   3

And the value to search: **2**
You should return this subtree:

  2
 / \
1   3

>Sol:
since it’s a BST, don’t need to go both left and right. If the current node’s value is bigger, only going right would do.

[Pascal's Triangle 2](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/3234/)
given row index, return that row’s element.
Input: rowIndex = 3
Output: [1,3,3,1]
>Solution:
[iterative] the same vector can be manipulated. Operating row-wise, just add (i-1)th ~ 0th element, later add another 1.

[Merge Two Linked Lists](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/2382/) (using recursion)

>Solution:
if the next of l1 is smaller, call recursively with l1->next and l2

[Kth Symbol in Grammar](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/1675/)

>Solution:
We don't need to actually generate the strings "0110..." (would be TLE error anyway)
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
We see that, for any level N, the first half of the string is the same as the string in N-1, the next half is just complement of it. The total number of items in level N is 2^N. The half mark of the string is marked by [2 ^(N-1)]-th item. So, for any level N:
if K is in the first half, it is same as the Kth element in level N-1
if K is in the second half, it is the complement of the number in [K-2^(N-1)]-th position in level N-1
So, we run the recursion until the base condition (N=1)

[Unique BST generation](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/2384/)
Generate all the BST from input n with the nodes (1...n).
>Sol: a [clean solution](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/2384/discuss/31575/24ms-c++-easy-understanding-solution)

[Search 2d Matrix](https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2872/)

>Sol:
approach 1: Search from top right. If the element is bigger than the target, theres no point searching in that column.

# All

[Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)

input: [ 2, 3, 4, 5 ]
output: [ 60, 40, 30, 24 ]
constraint: no division, O(n) solution exitst, both for space and time
>Solution 1 (with extra space):
Take two arrays left and right. where
left[i] will be the product of all elements before i.
right[i] will be the product of all elements after i.
Multiply them together and that’s the resulting array.

>Solution 2 (without extra space):
The left and right arrays aren’t needed if we use the final array as left/right array and then in another iteration use the last right/left result and multiply with itself.

[Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
>Solution:
We can keep track of lowest and highest products until now in two variables. If the current number is negative then these variables should be swapped. Then ith number are to be multiplied by both lowest and largest and kept only the largest of current and largest and lowest of current and lowest. The max of max and largest is the new max.

[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)
Input: s = "babad"
Output: "bab"
>Solution:
We take a bool matrix. The y-axis shows the start and x-axis shows the ending position and (x,y) takes true if start to end forms a palindrome. Then we take length=1 to string’s length and populate the matrix.
For length=1, the diagonals are marked true, since a single character is a palindrome.
For length=2, true is put if both the positions contain the same character.
For lengths more than 2, at first we look if the corners are equal. If they are, we see from the matrix if the others form a palindrome.

[Container With Most Water](https://leetcode.com/problems/container-with-most-water)
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
>Solution:
Start from the widest. Get inwards if higher than both columns is found.

[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
>Solution:
iterative: Take each digit, take the button’s string and add each characters with the strings we have in hand in all combinations, then replace the strings we had in hand with the newly generated ones.