Leetcode: Maximum Subarray (Dynamic programming)

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.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and 

conquer approach, which is more subtle.

Hide Tags

 Divide and Conquer Array Dynamic Programming

Show Similar Problems

1. Dynamic Programming ( O(log(n)) ):

Using max and temSum to save the previous results. 

////////////////////////

//codes

class Solution {

public:

       int maxSubArray(vector<int>& nums) {

              int sum = 0, max;

              if (nums.size() == 0)return max;

              max = INT_MIN;

              for (int i = 0; i<nums.size(); i++){

                     sum += nums[i];

                     //update the previous maximal value

                     if (sum>max)max = sum;

                     //discard the previous negtive sum

                     if (sum<0)sum = 0;

              }

              return max;

       }

};

**Leetcode: Merge Sorted Array (3ms) analysis and solution

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) 

to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Hide Tags

 Array Two Pointers

Show Similar Problems

Analysis:

1. Understand the problem clear first: merge the nums2 into nums1, which means that it's not a good idea to build the third vector, eg. nums3, to store the new vector. Instead, we need to merge in place.

2. Merge from back to front. This way we avoid the extra element moving operations. Note the condition when i<0;

//////////////////////////////////////////////////
//codes  4ms

class Solution {

public:

       void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

              int index = 0, i = m - 1, j = n - 1;

              //check input

              if (n == 0) return;

              else if (m == 0){ nums1 = nums2; return; }

              while (j>-1){

                     //judge the bigger one

                     if (i<0 || nums2[j] >= nums1[i]){

                           nums1[m + n - 1 - index] = nums2[j];

                           j--;

                     }

                     else {

                           nums1[m + n - 1 - index] = nums1[i];

                           i--;

                     }

                     index++;

              }

       }

};

//////////////////////////////////////////////////////////////////
Revised 3ms
///////////////////////////////////////////////////////////////////

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1, j=n-1, k=m+n-1;
        while(j>-1){
            if(i< 0 || nums1[i]<nums2[j]){ //Note: this branch should be put in front
                nums1[k]=nums2[j];
                j--;
                k--;
            }
         
            else{
                nums1[k]=nums1[i];
                i--;
                k--;
            }
         
         
        }
        return;
    }
};

Leetcode: Search for a Range (12ms) solution

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Hide Tags

 Array Binary Search

Show Similar Problems

Analysis:

A Binary search problem.


///////////////////////////////////////////////////////////////////
//code  12ms
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int m=nums.size(), l=0, r=m-1, mid=(l+r)/2, flag_find=0;
        //find target first
        while(l<=r){
            if(target<nums[mid]){
                r=mid-1;
                mid=(l+r)/2;
            }
            else if(nums[mid]<target){
                l=mid+1;
                mid=(l+r)/2;
            }
            else{
                flag_find=1;
                break;
            }
        }
        //search the range
        if(flag_find==1){
            //search left
            for(int i=mid-1;i>=0;i--){
                if(nums[i]!=target){
                    l=i+1;
                    break;
                }
                l=0;
            }
            //search right
            for(int i=mid+1;i<m;i++){
                if(nums[i]!=target){
                    r=i-1;
                    break;
                }
                r=m-1;
            }
            vector<int> res;
            res.push_back(l);
            res.push_back(r);
            return res;          
        }
        else{
            vector<int> res;
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
     
    }
};

Leetcode: Spiral Matrix (0ms) Analysis and solution

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Analysis:

Logic is not very difficult, but it has lots of trivial things inside. The procedure can be divided into 4 sections and then process the four sections individually. The key here is the boundary control. See following figure for a clear logic and procedure to implement this problem:

In the figure, four index are used to mark the boundary: upper, right, bottom and left. The code according to above procedure:

//////////////////////////////////////////////////////////
// code 0ms

class Solution {

public:

       vector<int> spiralOrder(vector<vector<int>>& matrix) {

              int upper = 0, right = 0, bottom = 0, left = 0;

              vector<int> res;

              //check input

              if (matrix.size() == 0)return res;

              int m = matrix.size(), n = matrix[0].size(), index = 0, Size = m*n;

              while (index < Size + 1){

                     //section 1

                     for (int j = left; j < n - right; j++){

                           res.push_back(matrix[upper][j]);

                           ++index;

                     }

                     upper++;

                     if (index >= Size)return res;

                     //section 2

                     for (int i = upper; i < m - right; i++){

                           res.push_back(matrix[i][n - right - 1]);

                           ++index;

                     }

                     if (index >= Size)return res;

                     right++;

                     //section 3

                     for (int j = n - right - 1; j >= left; j--){

                           res.push_back(matrix[m-bottom-1][j]);

                           ++index;

                     }

                     if (index >= Size)return res;

                     bottom++;

                     //section 4

                     for (int i = m - bottom - 1; i > upper-1; i--){

                           res.push_back(matrix[i][left]);

                           ++index;

                     }

                     if (index >= Size)return res;

                     left++;

              }

              return res;

       }

};

Leetcode: Minimum Size Subarray Sum (4ms) analysis and solution

PROLBEM:

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Analysis:

Using moving window to sweep from left to right, O(n):

1. initial window set as: left=0, right =0;  sum=0;
2. when sum < target, increase the right until the sum is >=target;
3. when sum >=target, update the minimal length if needed;
    remove the first component in sum;
    increase the left by one until sum<target;

NOTE some trivial marked as red in codes.

/////////////////////////////////////////////////////////////////////////
//code 4ms

class Solution {

public:

       int minSubArrayLen(int s, vector<int>& nums) {

              int l = 0, r = 0, n = nums.size(), sum = 0, len = -1;

              if (n == 0)return 0;

              while (r <= n){

                     //increase right   

                     if (sum<s){

                           if (r == n)break;

                           sum += nums[r];

                           ++r;

                     }

                     //increase left

                     else if (sum >= s){

                           int lenTmp = r - l;

                           if (len == -1)len = lenTmp;

                           else if (lenTmp<len)len = lenTmp;

                           else;

                           if (len == 1)return 1;

                           sum -= nums[l];

                           l++;

                     }

              }

              return len == -1 ? 0 : len;

       }

};

Leetcode: Pascal's Triangle (0ms)

Problem:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Analysis:

Refer to the link to see how Pascal's triangle works.
So basically compose the the current row members according to the previous row.

//////////////////////////////////////////////
//code  4ms
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
     
        for(int i=0;i<numRows;i++){
            vector<int> tmp;
            for(int j=0;j<i+1;j++){
                tmp.push_back(1);
                if(j>0 && j<i){
                    tmp[j]=res[i-1][j-1]+res[i-1][j];
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};



Using Backtracking: (3m)

class Solution {
public:
    void BT(vector<vector<int>> &res, int n){
        if(n==1){
            vector<int> tmp={1};
            res.push_back(tmp);
            //return;
        }
        else{
            BT(res,n-1);
            vector<int> tmp={1};
            for(int i=1;i<n;i++){
                if(i>res[n-2].size()-1){
                    tmp.push_back(1);
                }
                else tmp.push_back(res[n-2][i]+res[n-2][i-1]);
            }
            res.push_back(tmp);
            //return;
        }
    }
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if (numRows==0)return res;
        BT(res, numRows);
        return res;
    }
};

Leetcode: Plus ONE (4ms) solution

PROBLEM:

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Analysis:

Plus one from the end of the array. Key is to process the carrier from the addition.

///////////////////////////////////////////////////
// code 4ms
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size(), i = n - 1, c = 1;

while (i>-1 && c == 1){
int tmp = c;
            c = digits[i] + 1>9 ? 1 : 0;
digits[i] = (tmp + digits[i]) % 10;

i--;
}
//c is still 1
if (c == 1){
digits[0] = 1;
digits.push_back(0);
}
return digits;
}
};

Leetcode: Product of Array Except Self (60ms) analysis and solution

Problem:

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to 

the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not 

count as extra space for the purpose of space complexity analysis.)

Hide Tags

 Array

Show Similar Problems

Analysis:

Using two round processing: forward and backward. See figure for detail:

//////////////////////////////////////////
//code 60ms
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> tmp(nums.size(), 1);
        int n=nums.size();
        //forward
        for(int i=0;i<n-1;i++){
            tmp[i+1]=tmp[i]*nums[i];
        }
        //backward
        int m=1;
        for (int j=n-1;j>-1;j--){
            tmp[j]=m*tmp[j];
            m=m*nums[j];
        }
        return tmp;
    }
};

Leetcode: Remove Duplicates from Sorted Array (32ms) (two pointers) analysis and solution

Problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and 

return the new length. Do not allocate extra space for another array, you must do this in place 

with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 

respectively. It doesn't matter what you leave beyond the new length.

Hide Tags

 Array Two Pointers

Analysis:

A classical two pointer (TP) problem. Usually, TP is used when extra space is not allowed to be used. The key to use the TP is to get a clear idea about the logic of the problem first. Different problem can have different logic. The logic for this problem can be shown as following (you may use other logic!):
(click to see large and clear image)

s and i are two pointers used to mark left position and going sweeping position, respectively. 

///////////////////////////////////////

//code 32ms

class Solution {

public:

       int removeDuplicates(vector<int>& nums) {

              int s = 0, n = nums.size();

              if (n<2)return n;

              for (int i = 1; i<n;){

                     if (nums[i] != nums[s]){

                           if (i - s>1)nums[s + 1] = nums[i];

                           s++;

                           i++;

                     }

                     else i++;

              }

              return s + 1;

       }

};

by erasing the extra elements inside (39ms)

//////////////////////////////////////////////

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //edge case
        if (nums.size()<2)return nums.size();
        
        vector<int>::iterator ite=nums.end(), iteTmp=ite;
        iteTmp--;ite--;ite--;
        for (;iteTmp!=nums.begin();iteTmp--,ite--){
            if ( iteTmp!=nums.begin() &&*ite==*iteTmp){
                nums.erase(ite);
            }
            if (ite==nums.begin())break;
        }
        return nums.size();
    }
};

if only need to return the number of distinct elements without revising the vector nums:

/////////////////////////////////////////////////////////////////////////////
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size()<2)return nums.size();
        int len=1;
        for (int l=0, r=1; r<nums.size();){
            if (nums[l]==nums[r]){
                r++;
            }
            else {
                len++;
                l=r;
                r++;
            }
        }
        return len;
    }

};