Grind 75

Question 1

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.

Example 1 :
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

https://leetcode.com/problems/two-sum/

Answer 1

• Use HashMap
• Iterate through each item in given integers
• Check if target-current_item exist in the map
  
  • If exists return current index and value of target-current_item
  • Else put target-current_item as key and current index as value.

* Time complexity - O(n)
* Space Complexity - O(n)

Question 2

20. Valid Parentheses

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

Example 1 :
Input: s = “()[]{}”
Output: true

Answer 2

• Use Stack
• Iterate through each character in given string s
  
  • If the character is opening parenthesis, push it to Stack
  • Else pop the top of the stack and compare it with current character
    
    • If Pair (popped, current character) are valid bracket then continue
    • Otherwise return false
• After the loop the stack should be empty for valid otherwise invalid

* Time complexity - O(n)
* Space Complexity - O(n)

Question 3

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Return the head of the merged linked list.

Example 1 :
Input: list1 = [1,2,4], list2 = [1,3,4,5]
Output: [1,1,2,3,4,4,5]

Answer 3

• Iterate list1 and list2 together and keep moving next for the smaller value list (while(list1 != null && list2 != null)
• After first iteration
  
  • We are done. Do nothing. Or
  • list1 is exhausted, simply copy the remaining element to result list. Or
  • list2 is exhausted, simply copy the remaining element to result list

* Time complexity - O(m+n)

Question 4

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

Example 1 :
Input: prices = [7,1,5,3,6,4]
Output: 5

Answer 4

• Keep track of the minimum price and maximum profit while iterating through the list.
• Start with:
  
  • minPrice = array[0];
  • maxProfit = 0;

* Time complexity - O(n)

Question 5

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

Example 1 :
Input: s = “A man, a plan, a canal: Panama”
Output: true

Answer 5

• Two pointers solution
• Convert given sentence in uppercase
• while(left < right)
• Start with left(0) and right(len-1) pointers
• if left and right points to alpha numeric
  
  • if they are not equal, return false
  • else continue
• Otherwise move the pointer(s) which is/are pointing to non alpha numeric character
• True after coming out of loop

* Time complexity - O(n)

Question 6

226. Invert Binary Tree

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

Example 1 :
Input:
1
/ \
2 3
/ \ \
4 5 6
Output:
1
/ \
3 2
/ / \
6 5 4

Answer 6

• Use DFS or BFS to solve it
• Recursive Approach:
  *Swap the left and right children of the current node.
  *Recursively invert the left subtree.
  *Recursively invert the right subtree.

*Iterative Approach (BFS):
*Use a queue to perform Breadth-First Search (BFS).
*For each node, swap its left and right children.
*Add the left child (previously right) to the queue if it exists.
*Add the right child (previously left) to the queue if it exists.

* DFS - Time complexity - O(n)
* BFS - Time complexisity - O(n) and space complexity - O(n)

Question 7

242. Valid Anagram

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

Example 1 :
Input: s = “anagram”, t = “nagaram”
Output: true

Answer 7

• Use a HashMap to count frequency of each character
• Traverse both strings at the same time
• use s char to increase the count by 1
• use t char to decrease the count by 1
• After that iterate through hashmap and return false if any value is not equal to zero.

* Time complexity - O(n)
* Space complexity - O(n)

Question 8

704. Binary Search

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.

Example 1 :
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Answer 8

• Use two pointers.
• Start with left = 0, right = arr.length-1
• Iterate until two pointers crosses each other
• while(left <= right) and compute mid
• to avoid overflow use - mid = left + (mid-left)/2;

* Time complexity - O(logn)
* Space complexity - O(1)

Question 9

733. Flood Fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Example 1 :
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Answer 9

• Use DFS
• Start at the given cell (sr, sc).
• Recursively apply DFS to its four neighboring cells if they match the starting color.
• Use Directions array, global
• No need for visited list since coloring tells which cell is already visited and not called again
• Handle edge case when current cell is same as start color then do nothing

* Time complexity - O(m*n)
* Space complexity - O(1)

Question 10

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1 :
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Answer 10

• Use current and global max sum
• Initialise with first element
• Iterate from second element of num
• Decide if we add current element in current sum or start a new sum from current element max(currenSum+num[i], num[i]
• Keep updating global max

* Time complexity - O(n)
* Space complexity - O(1)

Question 11

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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).”

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition..

Example 1 :

Answer 11

• Use recursive solution
• if p and q are greater than root, search recursively in right subtree
• if p and q are less than root, search in left subtree
• otherwise root is the LCA

* Time complexity - O(n)
* Space complexity - O(1)

Question 12

236. Lowest Common Ancestor of a Binary Tree

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

Example 1 :
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Answer 12

• Recursive solution
• traverse in left subtree and right subtree
• if each call returns not null node then root is the LCA
• if both returns null, then LCA is null
• if left is not null, then left is LCA
• else right is LCA

* Time complexity - O(n)
* Space complexity - O(1)

Question 13

57. Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion

Example 1 :
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Answer 13

• Add intervals[i] in result. [intervals[i]'s endtime is before starttime of newInterval]
• Add newInterval in result. [newInerval endtime is before starttime of intervals[i]]
• Else it is overlapping. merge. [take min of starttime and max of endtime, it will be new newInterval]

* Time complexity - O(n)
* Space complexity - O(1)