Tag: java

  • 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…

  • Convert Roman to Integer

    Given a string representing a roman numeral , convert it into an integer. The values of each roman character is also given: Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, IV means 4 XX means 20 Try out the solution here: https://leetcode.com/problems/roman-to-integer/ Solution: Have a…

  • Word Search II

    Given a m*n board of letters and a list of words , find those words present in the board. For example, Given the board: and the below list of words: [“oath”,”pea”,”eat”,”rain”] The output is “eat” ,”oauth” Try out the solution here: https://leetcode.com/problems/word-search-ii/solution/ Solution: Let’s use Trie data structure to solve this problem. We could use…

  • A Word dictionary for adding and searching words

    Create a word dictionary to add and search words. You can also search using ‘.’ regular expression, That is searching for the word “.at” will return true if the dictionary contains words like cat , mat etc since the first letter can be anything. Try out the solution here: https://leetcode.com/problems/design-add-and-search-words-data-structure/ Solution: The solution to this…

  • How to implement Trie Data Structure?

    Trie is a datastructure useful to store set of words. It is a tree with a lot of children , one for each letter of the alphabets. So if you want to store lower case English letter words each node can have unto 26 child nodes. Every word is represented by as many nodes as…

  • Find the Lowest Common Ancestor of two given nodes of a Binary Search Tree

    Given two nodes and the root node of a binary search tree, Find the lowest common ancestor of those two nodes. A common ancestor node is a node who is the parent of both the given nodes. Lowest common ancestor means there is no other common ancestor node which is lower than this node in…

  • Kth Smallest Element in a Binary Search Tree

    Given a binary search tree, find the kth smallest element in it. For example, For the below tree: If k = 3, Then the kth (3rd) smallest element is 3. If k = 2, Then the output is 2. Try out the solution here: https://leetcode.com/problems/kth-smallest-element-in-a-bst/ Solution: Hint : Use inorder traversal. Explanation: Approach 1 –…