# Category Archives: Arrays

View algorithms on Arrays

## The Stock Market Problem

Question: Let us suppose we have an array whose ith element gives the price of a share on the day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. When we talk about the best… Read More »

## Separate 0’s and 1’s in an array.

Question: Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array. Input: 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 Output: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 The objective of the… Read More »

## Separate odd and even numbers in an array.

Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers. Input: 4, 8, 15, 16, 23, 42 Output: 4, 8, 16, 42, 23, 15 The objective of this problem is mainly to segregate the array in two halves. One half… Read More »

## Find the majority element in an array. (Method 3)

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element =… Read More »

## Find the majority element in an array. (Method 2)

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element =… Read More »

## Find the majority element in an array.

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element =… Read More »

## Find the number of occurrences of an element in a sorted array. (Method 2)

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 We discussed the basic method to find the number of occurrences in this post. But here, in both the cases, the time… Read More »

## Find the number of occurrences of an element in a sorted array.

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 The most basic methodology to solve this problem is linear search. Just scan the array and count the number of occurrences. But… Read More »

## Find the index of last occurrence of an element in a sorted array.

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the last occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 4 (0 based indexing) This problem is very much similar to the binary search problem. We… Read More »

## Find the index of first occurrence of an element in a sorted array.

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the first occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 2 (0 based indexing) This problem is very much similar to the binary search problem. We… Read More »