Monthly Archives: September 2012

Longest Valid Parentheses

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. C++: 01 int longestValidParentheses(string s) 02 { 03     stack<int> tmp; 04     int n=s.size(); 05     int max=0; 06    … Continue reading

Posted in Array and linked list, Stack and Queue, String | Leave a comment

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6. More practice:If you have figured out the O(n) solution, try coding … Continue reading

Posted in Array and linked list | Leave a comment

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). C++: 01 double kSmall(int A[],int m,int B[],int n,int k) 02  … Continue reading

Posted in Array and linked list, Binary search | Leave a comment

Merge Intervals

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. C++: 01 vector<Interval> merge(vector<Interval> &intervals) 02 { 03      vector<Interval> result; 04      int n=intervals.size(); 05      if(n==0) 06          return result; 07  … Continue reading

Posted in Array and linked list | Leave a comment

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. C++: 01 void enList(ListNode*& head, ListNode*& tail, ListNode* p) 02 { 03      if(p==NULL) 04          return; 05      if(head==NULL){ … Continue reading

Posted in Array and linked list | Leave a comment

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. C++: 01 void reverse(string& a) 02 { 03     int n=a.size(); 04     for(int i=0;i<n/2;i++){ 05      … Continue reading

Posted in Number trick, String | Leave a comment

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”. Note: If there … Continue reading

Posted in String | Leave a comment