Array Implementation of Heap

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays. So, suppose we have following heap (having 9 elements) : Now, we need array of 9 elements. Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled. Now, we start putting the elements one by one. [Read More]
kodeknight  array  heap  Data Structure 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find Nth largest element in the rotated sorted array So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don’t know. [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find the rotation count in rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. [Read More]
ArraySearch  kodeknight  recursion  array  rotated array  count  min  sorted-array 

Operation time complexity for an ARRAY

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

The time complexity of handling the operations in a data structure like an ARRAY are as follows:

i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.

kodeknight  time complexity  array  Data Structure  operations 

What is a linear datastructure?

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Linear datastructure is one in which the data items are placed in the memory contiguously i.e. one after the other. Pros If we search the first data item, then it is very easy to find the next data items Cons Size of the array must be know prior to allocation Requires contiguous memory, however if a free memory space is disjoint then this free memory space is not utilized for memory allocation Example of linear datastructure is an array. [Read More]
kodeknight  array  Data Structure  Linear datastructure 

Selection Sort

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort. Pseudocode of selection sort Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position …. [Read More]
cpp  kodeknight  c  array  Selection Sort  Sorting Algorithm  sorting arrays  sorting  In-place sorting  Data Structure  Comparison Sort  java 

How to rotate an array?

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

One of the classic problems with array is to perform in-place rotation on the array. For example, if we have an array of integers such as int[]array = new int[]{1, 2, 3, 4, 5, 6} and we want to rotate it around index 2, then the rotated array is {3, 4, 5, 6, 1, 2}. So, how can we rotate an array around a given index? Well here is the algorithm with explanation follows after: [Read More]
kodeknight  array  rotated array 

2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

how to build the hash table in the approach 3. als… Unknown - Feb 3, 2014how to build the hash table in the approach 3. also i think you should check if hash(T-arr[i]) is empty first. This comment has been removed by the author. Hi Jianchen, I think we can use hashmap or we can use element as an index in the array. I think only way hash() is empty when the given array is null or has no element. [Read More]
kodeknight  2Sum  sorting  array  hashtable  pair  unique  sum