Simple Array

Get number occurring Odd time
Way I. Hash table, with array elements as key, and count as value
Way II. Do bit-wise XOR of all elements,

Reverse Array
void revarr(int arr[], int start, int end)
Iterative:   while(start<end) { swap(arr[start], arr[end]); start++; end--; }
Recursive: if(start>=end) return; swap(arr[start], arr[end]); revarr(arr, start+1, end);

Rotate Array
I. Rotate by one until d rotations
void rightRotateOnce(int arr[], int times)
  for(int i=0; i<times; i++) rightRotateOnce(arr, times);
void rightRotateOnce(int arr[], int len)
  tmp=arr[0];
  for(int i=n-1;i>0;i++) arr[i-1]=arr[i];
  arr[i]=tmp;

for(i=0;i<d;i++) leftRotateOnce(arr, n);  //Caller   Time:O(n*d) Space: O(1)

II. Rotate in chunk until d rotations O(n) time, O(1) space

Instead of one by one movement, divide array into sets=GCD(n,d)

arr[]={10,20,30,40,50,60,70,80,90,100,120};   gcd(12, 2) = 3

I. arr[]={40, 20, 30, 70, 50, 60, 100, 80, 90, 10, 110, 120};

II.arr[]={40, 50, 30, 70, 80, 60, 100, 110, 90, 10, 20, 120}; 

III. arr[]={40, 50, 60, 70, 80, 90, 100, 110, 120, 10, 20, 30};

int gcd(int a, int b)

{ if(b==0) return a;
   else return gcd(b, a%b);
}
void leftRotate(int arr[], int size)
{
   int i, j, k, tmp, loop_end
   loop_end = gcd(d,n);
   for (i = 0; i < loop_end; i++)
   {
     /* move i-th values of blocks */
     tmp = arr[i];        j = i;
     while(1)
     {
       k = j + d;
       if (k >= n)     k = k - n;
       if (k == i)      break;
       arr[j] = arr[k];         j = k;
     }
     arr[j] = tmp;
}

III. Rotate using array reversal
Logically break array using indexes into two parts, 1..d and (d+1)..n
Reverse Each part, Reverse All
   revarr(arr[], 1, d)
   revarr(arr[], d+1, n)
   revarr(arr[], 1, n)

Get Max Occuring Element
Add to BST, keep count of element. O(n^2).
Use self-balancing BST, O(nlogn).

Find max diff such that larger appear after smaller O(n)
I) Take difference with min element found so far(instead of each element), and keep track of max_diff and min_elem. Init max_diff=arr[1]-arr[0]; and min_elem=arr[0].
or,
II) Find difference between adjacent elements, store in diff[]. Find max sum subarray on diff[].
or
Optimize: Do without storing diff[]
int max_diff(int arr[], int n)
{ int diff=arr[1]-arr[0];  int current_sum=diff; int max_sum=current_sum;
   for(i=0;i<n-1;i++)
      diff=arr[i+1]-arr[i];
      if(current_sum>0)  current_sum+=diff;
      else                         current_sum=diff;
      if(current_sum>max_sum)  max_sum=current_sum;
   return max_sum;
}

Find kth largest element
Build max heap, extract max k times.

Segregate Odd/Even
while(left<right)
    Keep left++ until odd elem, keep right-- until even elem.
    if(left<right) swap arr[left, arr[right)


Sort Arrays of 0,1,2 in single pass
void swap(int *a, int *b){ int t=*a; *a=*b; *b=tmp;}
sort012(int arr[], int size)
{
   int left=0, right=size-1, mid=0;
   while(mid<=right)
   {
      switch(arr[mid]){
        case 0: swap(&arr[low], &arr[mid++]); break;
        case 1: mid++; break;
        case 2: swap(&arr[mid], &arr[right--]; break;
       }
   }
}

Largest Sum Contiguous Sub-array


Reference
Full List @ Geeks