-
✱✱✱ 79. Word Search Leetcode Problem Solution
In this problem we use the concept of backtracking, whenver we find a character matching the first character of our word we check the solution there if it is possible, for that we make four choices as we can move in four diretions left, right , upside and down and backtrack if we don’t find the solution while traversing one of our possible paths. 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 class Solution: def check_word(self,board,word,r,c): if word[0] == board[r][c] and board[r][c] is not None: char_is = board[r][c] board[r][c] = None word = word[1:] if len(word) == 0: return True if (r+1 < len(board) and self.
Read more… -
{ Leetcode } 150. Evaluate Reverse Polish Notation
We are maintaining a stack to evaluate this reverse polish expression, as soon as we find an operator we replace the top two most elements of the stack with the result and in the end, we get the answer at the top of our stack. 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 Solution: def evalRPN(self, tokens: List[str]) -> int: #expression stack expr = [] ans = 0 operators = {'+','-','/','*'} for t in tokens: if t in operators: #evalutate op1 = expr[-2] op2 = expr[-1] if t == '+': ans = op1 + op2 elif t == '/': if op2 == 0: ans = 0 elif op1 < 0 and op2 > 0: ans = (-1* op1) // op2 ans = ans * -1 elif op1 >0 and op2 < 0: ans = op1 // (op2 * -1) ans = ans * -1 else: ans = op1 // op2 elif t == "*": ans = op1 * op2 else: ans = op1 - op2 expr.
Read more… -
Leetcode 19. Remove Nth Node From End of List
We are using a hashmap or dictionary to maintain indexes of node as we traverse them, as soon as we finish traversing we get the nth node from the back by subtracting it from the last node + 1, +1 as we move ahead of the last node and reach null see code to clarify this little thing, we make the pointer of the n-1’th node pointing to n+1’th node.
Read more… -
Leetcode 34 -> Find First and Last Position of Element in Sorted Array
We use the modified binary search here, when we find the element we don’t break our binary search, instead we keep on moving, One time towards left and another time towards the right to find the left most and right most index of our target. The below code illustrates the approach more clearly. 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 class Solution: def bin_search(self,nums,target,lr): n = len(nums) low = 0 high = n-1 tfound = None while low<=high: mid = (low+high)//2 if nums[mid] == target: tfound = mid if lr == "left": high = mid-1 else: low = mid + 1 # break elif target < nums[mid]: high = mid - 1 else: low = mid + 1 if tfound == None: tfound = -1 return tfound def searchRange(self, nums: List[int], target: int) -> List[int]: n = len(nums) lb = self.
Read more… -
Leetcode 134. Gas Station solution in Python 3 programming language
We start our journey at each gas pump and check whether we reach the starting pump or not, just see the code below to get the grasp of the approach used for this problem. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: n = len(gas) for starting_pump in range(n): tank = gas[starting_pump] cost_to_next_pump = cost[starting_pump] next_pump = starting_pump while tank >= cost_to_next_pump: tank -= cost_to_next_pump next_pump = (next_pump + 1)%n if next_pump == starting_pump: return starting_pump tank += gas[next_pump] cost_to_next_pump = cost[next_pump] return -1
-
Leetcode 56. Merge Intervals Python 3 Solution
For this problem first, we sort all the intervals in increasing order of the starting values of intervals which will take O(N log N) time. We maintain a stack where we keep on checking the top most value of stack if the current iterated elenent is overlapping with the top most element of stack then we update our stack, if the interval is non-overlapping we just simply append it in our stack.
Read more… -
Leetcode 210 Course Schedule II Python 3 Solution
Approach - We will first create a graph out of this problem, Every pre-requisite course is connected to the course so the Pre=requisite course will be directing towards the course so we will create a Directed Acyclic Graph. We will find if there is any cycle in the graph and if it is so then taking all the courses will not be possible. To find if there is any cycle in the graph we will use an earlier discussed approach we took in Course Schedule I.
Read more… -
Leetcode 139 Word Break Python 3
Approach - We use dynamic programming in our solution. we first initialize our DP array with false at each index of character. We make our dp[i] as true when we have a word ending at i’th index in our dictionary and for that, the character before starting of this word in our string must also mark the end of the word. so in this way, our answer is at the last index of our DP array.
Read more… -
Letcode 148 Sort List Python 3 Solution
Approach - We use a merge sort for solving this problem it has to be done in O(N log N) and constant space O(1). We use the idea of merge sort where we first divide the list into two halves, doing so in an Array is easy but in a linked list, you have to do something different. We use the concept of fast and slow pointers where fast pointer traverses directly at a gap of two nodes whereas slow pointer traverses one at a time.
Read more… -
Leetcode 334 Increasing Triplet Subsequence - Python Solution
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Approach - We take two variables a and b . We initialize them to the biggest number in the array and then we iterate over the list and if a value is found less than the current value of a and b we change them. If a value greater than both of them is found then we return True which means we have found increasing subsequence.
Read more…