Category Archives: Divide and Conquer

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this … Continue reading

Posted in Divide and Conquer | Leave a comment

Quick sort

C++: 01 void quicksort(int A[], int l, int u) 02 { 03   int i, m; 04   if(l>=u) return; 05   swap(A, l, randint(l,u)); 06   m=l; 07   for(i=l+1;i<=u;i++) 08     if(A[i]<A[l]) 09       swap(A,++m,i); 10   swap(A,l,m); 11   quicksort(l,m–1); 12   quicksort(m+1,u); 13 }

Posted in Divide and Conquer | Leave a comment

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example,  Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this … Continue reading

Posted in Array and linked list, Divide and Conquer | Leave a comment

Pow(x, n)

Implement pow(x, n). C++: 01 double pow(double x, int n) { 02        if(n==0) 03            return 1; 04        if(n==1) 05            return x; 06        bool … Continue reading

Posted in Divide and Conquer | Leave a comment

Searching a 2D sorted matrix

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is, Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]. C++: … Continue reading

Posted in Divide and Conquer | Leave a comment

Convert sorted array to balanced binary search tree (BST)

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. C++: 01 Node* buildArrayBST(int *A, int size, int start, int end) 02 { 03     if(start>end) 04         return NULL; 05     int … Continue reading

Posted in Array and linked list, Divide and Conquer, Tree | Leave a comment