Find Local Minimum in an unsorted array with unique elements

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-local-minima-in-a-given-array/. Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1]. Examples: a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs Solution: Brute...

Read More

Sorted Linked List to Balanced BST

Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List. Example :  Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \ 2 6 / \ / \ 1 3 4 7 Lets discuss 2 approaches for this problem. Solution Method 1 (Simple) Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed. 1) Get...

Read More

Convert sorted array to Balanced BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/convert-sorted-array-to-height-balanced-binary-search-tree/. Problem  Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height. Examples Input: 1 2 3 4 5 6 7 Output: 4 / \ 3 6 / \ / \ 3 4 6 7 Solutions  Method 1 - Take the array's middle element and insert it recursively Pick up the middle element of the array Set...

Read More

Implement a stack using 2 queues

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-stack-using-queues/. Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution   A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping...

Read More

Stack with find-min/find-max in O(1) time

Problem Stack with find-min/find-max in O(1) time Solution Method 1 - using extra stacks for min and max The basic idea of the solution can be found here. Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element. Now the operations will be following  : push: - If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well. - Else, push the top element of 'min_stack' again on 'min_stack'. Similarly for max_stacks pop: -...

Read More

Algorithm Introduction

Definition:  An algorithm is a finite set of discrete statements (or Steps) in some particular sequence (or Order) to accomplish a predefined particular task. Properties:   An algorithm must have the following properties: Input(s)      : An algorithm must have one(1) or more pre-specified input(s). Output(s)     : An algorithm must have one(1) or more output(s). Definiteness  : Each steps of an algorithm must define clearly (i.e. without any confusion or Contradiction or Ambiguity). Finiteness   ...

Read More

Find the minimum and maximum in the array

Here are few question we find on finding min and max in the array, but array type changes. Unsorted 1D array Find the maximum (OR minimum) in an array Find the maximum AND minimum in an array with min number of comparisons Find the max and second maximum in an array (likewise for minimum) Find the max and nth max in an array Rotated Sorted array Find the minimum element in the rotated sorted array. Find Nth largest element in the rotated sorted array...

Read More

Find Maximum Value in the unsorted array

Problem :  Find Maximum Value in the unsorted array Solution Method 1 - Linear search Here is the code to do that : public int findMax(int[] numbers) { int max = 0; for (int i = 0; i < numbers.length; ++i) if (numbers[i] > max) max = numbers[i]; return max; } So, in worst case the number of comparisons will be (n-1). Time complexity - O(n)...

Read More

Find kth largest in an Array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/kth-largest-element-in-an-array/. Problem :   You have an array of numbers; you need to find the k-th largest in the arra  Solution Method 1 - Tournament principle We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build...

Read More

find out the largest and second largest number in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-second-largest-element-in-an-array/. Question: Write an efficient C program to find smallest and second smallest element in an array. Solution Method 1 - Compare each element with current max and second max Algorithm 1) Initialize both first and second smallest as a[0] first = second...

Read More

How to find max. and min. in array using minimum comparisons?

Problem : Given an array of integers find the max. and min. using minimum comparisons. Solution Method 1 (Naive) - Iterate through the array, and update min and max pointers 1. Iterate through the array, select element a 2. Update min by comparing (min, a) 3. Update max by comparing (max, a) Number of comparison here will be ~2N, if N is number of element. Time complexity will be O(n) though. Method 2 - Pick 2 elements at time, compare them and compare them with corresponding min and max 1. Pick 2 elements(a, b), compare them. (say a >...

Read More

Determine if a small tree T2 is the subtree of a huge tree T1

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/subtree-of-another-tree-problem/. You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. Solution Method 1 - Traversing through T1 and finding subtree at each node, if T1's node = T2.root Here's what we will do: Traverse T1.  If the current node is equal to the root node of T2, traverse...

Read More

Create linked lists of all the nodes at each depth for a BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/create-linked-lists-of-all-the-nodes-at-each-depth-for-a-binary-tree/. Problem Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists) Example So a binary tree such as : (1) / \ / \ (2) (3) / \ / \ (4) (5) (6) (7) Will return linked...

Read More

Find if there is a path between two vertices in a directed graph

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-if-path-exists-in-directed-graph-problem/. Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph. BFS to check the connectivity public enum State { Unvisited, Visited, Visiting; } public static...

Read More

How to check whether a given number n belongs to fibanocii series?

The standard way (other than generating up to N) is to check if (5N2+4) or (5N2−4) is a perfect square.  Had discussion with my friend, on this and hence I thought its a good information to share via blog. More -  http://math.stackexchange.com/questions/9999/checking-if-a-number-is-a-fibonacci-or-n...

Read More

Find next higher number using exact same digits

Problem Given a number X find the number Y which is next higher number than X using the exact same digits as in X. Example For example: given 38276 return 38627 Solution Method 1 - Brute force The brute-force method is to generate the numbers with all digit permutations and consider all the higher numbers than the given number and return the minimum number from those higher numbers. code - int findNext(int n) { int nextNum = INT_MAX; String nStr = Integer.toString(n); for(String perm : permutations(nStr)) { ...

Read More

Stack of plates

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/stack-of-plates/. Question  Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should...

Read More

Implementing 2 stacks in an array

Problem:   How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space? Lets denote the stacks by suffix 1 and 2. Now we have to implement the following methods : push1(int x) –> pushes x to first stack push2(int x) –> pushes x to second stack pop1() –> pops an element from first stack and return the popped element pop2() –> pops an element from second stack...

Read More

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/set-matrix-zeros-problem/. Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and  column is set to 0 Example Input :  1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution In this approach we can do : Scan the matrix,...

Read More

Rotate n * n matrix by 90 degrees

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-n-x-n-matrix-by-90-degrees/. Problem Rotate the n*n matrix by 90 degrees. Another way to ask the same problem    Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? Example ...

Read More

Determine if a string has all unique characters

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/determine-if-a-string-has-all-unique-characters/. Problem: Implement an algorithm to determine if a string has all unique characters. Solution Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2)...

Read More