Linear Search vs Binary Search

Earlier we have seen linear search and binary search and how these work individually, In this article we will compare these two search algorithms. If you are new to these, please read the prerequisites below- Prerequisites: Linear Search Binary Search SNo Linear Search Binary Search 1 Works with a sorted or unsorted array. Works with … Read more Linear Search vs Binary Search

Longest substring with at most two unique characters

Objective: Given a string, write an algorithm to find the longest substring with at most two characters. Example: Input: aabbccddc Output: ccddc, length: 5 Input: aabacbeeeebeaabb Output: beeeebe, length 7 Input: aaaaaa Output: Only one unique character is present in the input string Approach: Brute Force Identify all the substrings of the given input string … Read more Longest substring with at most two unique characters

Java program to find the largest element in array

Objective– Given an array of numbers, write a java program to find the largest element in the given array. Example: int [] a = {1, 5, 3, 9, 2, 8, 2} Largest Element: 9 Approach: Linear Search Initialize a variable largest_element = a[0]. Run a loop from 2nd element till the last element in the … Read more Java program to find the largest element in array

Find the element which appears maximum number of times in the array.

Objective: Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array. Example: int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; Output: Element repeating maximum no of times: 5, maximum count: 3 Approach: Naive approach: … Read more Find the element which appears maximum number of times in the array.

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, 2, 5}; Output: Array has duplicates : 2 int a [] = {1, 6, 5, 2, 3, 3, 2}; Output: Array has duplicates : 2 , 3   Approach: Naive approach: Use 2 loops. Check … Read more Find duplicates in an given array in O(n) time and O(1) extra space.

Track the Maximum Element in a Stack.

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

Approach:

  • Create another another Stack(call it as track) which will keep track of maximum in the given Stack(call it as main).
  • When you insert an element in the main stack for the first time ( 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 which ever 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 the element in the track Stack. . See Example below.

Thanks Gaurav Dey for suggesting this solution.

Read moreTrack the Maximum Element in a Stack.

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 which 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 to a array and using 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 moreFind a peak element in a Given Array