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

 Posted on February 19, 2014  (Last modified on August 11, 2020)  |  3 minutes  |  Kinshuk Chandra

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. [Read More]
max  kodeknight  minmax  O(1)  stack  min 

Find the minimum and maximum in the array

 Posted on February 16, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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. [Read More]
max  kodeknight  Page  minmax  2DSortedArray  unsorted-array  min  sorted-array 

Find kth largest in an Array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

**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 a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]
max  kodeknight  largest  minmax  unsorted-array  kth-largest  min  smallest 

find out the largest and second largest number in an array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

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 a00 first = second = a00 2) Loop through all the elements. a) If the current element is greater than firstMax, then update firstMax and secondMax. b) Else if the current element is greater than second then update secondMax pseudocode [Read More]
max  kodeknight  largest  minmax  unsorted-array  min  second-largest 

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

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

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. [Read More]
max  kodeknight  browserstack  minmax  array  unsorted-array  min