Find duplicates in an given array in O(n) time and O(1) extra space.

Objective: Given an array of integers, find out duplicates in it. Example: int [] a = {4, 6, 2, 1, … Read more

Track the Maximum Element in a Stack.

Objective: In a Stack, keep track of the maximum value in it. It might be the top element in the stack but once it is popped out, the maximum value should be from the rest of the elements in the stack.

Approach:

  • Create another Stack(call it track) which will keep track of the maximum in the given Stack(call it main).
  • When you insert an element in the main stack for the first time (which means it is empty), insert it in the track Stack as well.
  • Now onwards when you insert a new element(say it is x) in the main Stack, peek() the element from the track Stack ( say it is ‘a‘). Compare x and a and whichever is greater, insert it into track Stack.
  • When you pop the element from the main stack, pop from the track Stack as well
  • So to get to know the maximum element in the main Stack, peek at the element in the track Stack. . See the Example below.

Thanks, Gaurav Dey for suggesting this solution.

Read more

Find a peak element in a Given Array

Objective: In this article, we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.

Peak Element: peak element is the element that is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Output: A peak element and its index

Approach:

A simple approach is to do a linear scan of an array and using a few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

The answer is yes, by using Binary Search techniques.

Read more