Category: Algorithms
-
Sort three colors in an array
Given an array containing three different colors red ,white and blue denoted by numbers 0,1 and 2 sort the array such that red comes first followed by white followed by blue. Constraints: For example, Given the input: [2,0,1,0,2,1] The output is [0,0,1,1,2,2] Try out the solution here: https://leetcode.com/problems/sort-colors/ Solution: Approach 1 – Count the number…
-
Find the element which appears more than half the array size
Given an array, find the majority element which appears more than half the size of the array. Constraints: For example, in the below array: [7,6,8,7,7,7] The output is 7 since it appears 4 times which is more than half the size of the array (3) Solution: Finding a solution with O(n) extra space is easier.…
-
Single non duplicate number in an array
Given an array with all elements repeated twice except one element find out that element. Constraints: The time complexity should be O(n) Space complexity should be O(1) For example: Given the array : [1,3,4,3,4] the output is 1 since it occurs only once. Try out the solution here: https://leetcode.com/problems/single-number Solution: If we can use extra…
-
Is a Tree Symmetric?
Given a binary tree find out if it is symmetric or not. A tree is symmetric if it is left sub tree is a reflection of its right sub tree. Note that symmetry doesn’t mean left sub tree is equal to right sub tree. The following tree is a symmetric tree: As you see the…
-
Valid Sudoku
Given a board of size 9 * 9 representing a sudoku game , find out if it is valid. It is valid if : For example, The below sudoku: represented by the array: Input: board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”] ,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”] ,[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”] ,[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″] ,[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″] ,[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″] ,[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”] ,[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″] ,[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]] is valid since it obeys all the three conditions. Try…
-
Merge Sorted Array
Given two sorted arrays and their sizes , merge the two into the first sorted array. Extra space equal to the size of the second array is provided at the end of the first array. For example, Given the arrays: num1 = [1,2,3,0,0,0] , size = 3 ( remaining space for the second array to…
-
Inorder traversal of a Tree
Given the root node of a Tree , return the node values in a list in inorder. For example, For the below tree: The inorder traversal is [ 0,2,3,4,5,6,7,8,9] Try out the solution here: https://leetcode.com/problems/binary-tree-inorder-traversal Solution: There are three ways to do inorder traversal: Let’s look into each of them. Approach 1 – Recursion: In…
-
Plus One on an array
Given an array representing a integer with each index representing each digit starting from the most significant digit to the least, add one to the integer and return the output as an array. For example, For the input [1,6,7], The output is [1,6,8] For the input [9,9], The output is [1,0,0]. Try out the solution…
-
Remove Duplicates from Array
Given a sorted array (in ascending order) remove the duplicates from them . you should not use any extra memory. So to remove in place , you need to move all the unique elements to the left of the array. So if there are k unique elements in an array of length n, the first…
-
Longest Common Prefix
Given an array of strings , find the longest common prefix among them. For example, If you are given the strings “flower”,”flow”,”flight” , The longest common prefix among them is “fl”. Try out the solution here: https://leetcode.com/problems/longest-common-prefix/ Solution: You can solve this problem in multiple ways. We will look into three approaches: Horizontal Scanning: In…
