Scribd
Upload
104 views7 pages

Array Sorting and Algorithms Guide

The document discusses several algorithms: 1) Alternate sorting - Sorting arrays in different ways like counting frequencies or sorting arrays with 0s, 1s and 2s. 2) Kadane's algorithm - Finds the contiguous subarray with the largest sum within linear time complexity. 3) Finding subarrays with a given sum - Several approaches including using hashmaps or sorting to find subarrays with a given sum in linear or quadratic time. 4) Next greater element using stack - Finds the next greater element for each element using a stack in linear time complexity.

Uploaded by

Hari Venkatesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
104 views7 pages

Array Sorting and Algorithms Guide

The document discusses several algorithms: 1) Alternate sorting - Sorting arrays in different ways like counting frequencies or sorting arrays with 0s, 1s and 2s. 2) Kadane's algorithm - Finds the contiguous subarray with the largest sum within linear time complexity. 3) Finding subarrays with a given sum - Several approaches including using hashmaps or sorting to find subarrays with a given sum in linear or quadratic time. 4) Next greater element using stack - Finds the next greater element for each element using a stack in linear time complexity.

Uploaded by

Hari Venkatesh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

1.

Alternate Sorting

Space complexity:- O(1)


2. Count frequencies of all elements in array from 1 to n in O(1) extra space
and O(n) time

3. Sort an array of 0s, 1s and 2s(Dutch National Flag Problem)


Time Complexity: O(n)
class DutchNationalFlag {

static void sort012(int a[], int arr_size)

int lo = 0;

int hi = arr_size - 1;

int mid = 0,temp=0;

while (mid <= hi)

switch (a[mid])

case 0:

//swap(low,mid)

temp = a[lo];

a[lo] = a[mid];

a[mid] = temp;

lo++;

mid++;
break;

case 1:

mid++;

break;

case 2:

//swap(mid,high)

temp = a[mid];

a[mid] = a[hi];

a[hi] = temp;

hi--;

break;

default:

mid++;

/* Utility function to print array arr[] */

static void printArray(int arr[], int arr_size)

int i;

for (i = 0; i < arr_size; i++)

System.out.print(arr[i]+" ");

System.out.println("");

/*Driver function to check for above functions*/

public static void main (String[] args)

int arr[] = {0,1,2,0,1,2,3,4,6,0,1,2};

int arr_size = arr.length;

sort012(arr, arr_size);

System.out.println("Array after seggregation ");

printArray(arr, arr_size);
}

4.Kadanes Algorithm
Time Complexity:O(n)

Here we do s=i+1 bcos there is no hope that we will find greater element before i.So we extend I
to next position

5.Sub Array with Given sum


a.O(n)^2 -This is normal approach
b.O(n)
If the question askd you to print index then go for hashmap

c.If question asks you to print pairs go for hashset


d.O(nlogn) using sorting algorithm everyday-youtube based on a a default
sorting method
6.Next Greater element using stack O(n)

You might also like