Product of Array Except Self

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].

Approach:

The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ vector<int> productExceptSelf(vector<int> &nums) { int numsSize = nums.size(); vector<int> result(numsSize); int temp = 1; // stores the product on the left of each element excluding itself for(int i = 0; i < numsSize; i++){ result[i] = temp; temp = temp * nums[i]; } temp = 1; // stores the product on the left times product on right of each element excluding itself for(int i = numsSize - 1; i >= 0; i--){ result[i] = result[i] * temp; temp = temp * nums[i]; } return result; }

Read More

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

bool isPalindrome(char* s) { int i, j, len; len = strlen(s); i = 0; j = len - 1; while(i < j){        // skip non alpha chars from start        while(i < len && !isalnum(s[i])){ i++; }         // skip non alpha chars from end        while(j >= 0 && !isalnum(s[j])){ j--; }         if(i < j && tolower(s[i]) != tolower(s[j])){ return false; }         i++; j--; } return true; }

Read More

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Approach : Use the simple recursive solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool checkIfSymmetric(struct TreeNode* n1, struct TreeNode* n2){ if(n1 == NULL && n2 == NULL) return true; if(n1 == NULL || n2 == NULL) return false; if(n1->val == n2->val){ return checkIfSymmetric(n1->left, n2->right) && checkIfSymmetric(n1->right, n2->left); } return false; } bool isSymmetric(struct TreeNode* root) { if(root == NULL){ return true; } return checkIfSymmetric(root->left, root->right); }

Read More

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Approach : The standard recursive solution times out so the idea is to use the iterative solution to find the nth fibonacci number.

int climbStairs(int n) {
    int f1 = 2;
    int f2 = 1;
    if(n == 1) {
        return f2;
    } else if(n == 2) {
        return f1;
    }

    int fn;
    for(int i = 3; i <= n; i++) {
        fn = f1 + f2;
        f2 = f1;
        f1 = fn;
    }
    return fn;
}

Here is the link to the ideone solution : http://ideone.com/ErEU6E

Read More

38. Count and Say

Problem: The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1

2.     11
3.     21

4.     1211

5.     111221

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1

Output: "1"

Example 2:

Input: 4

Output: "1211" 

Approach: The solution is straight forward. The appendNext method is run over n times where n is the input.

class Solution {
public:
    public:
 
    string appendNext(string str){
        string str1;
        char ch = str[0];
        int chCount = 1;
        for(int i = 1; i <= str.size(); i++){
            if (str[i] == ch){
                chCount++;
            }
            else {
                char chr = chCount + '0';
                str1 = str1 + chr;
                str1 = str1 + ch;
                ch = str[i];
                chCount = 1;
            }
        }
        return str1;
    }
    
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        string str1 = "1";
        string strn;
        for (int i = 1; i < n; i++){
            strn = appendNext(str1);
            str1 = strn;
        }
        return strn;
    }
};

Here is the link to the ideone solution : http://ideone.com/tbYXUM

Read More

283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Approach: Bring forward the non-zero values using a for loop and then fill the zeros at the end. 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0, n = nums.size();
        //move the non-zero elements to the front
        for(int i = 0; i < n; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        //fill the remaining right indices with zeros
        for(int i = j; i < n; i++){
            nums[i] = 0;
        }
    }
};

Here is the link to the ideone solution : http://ideone.com/O0MRQa

Read More

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Approach 1: Use modified binary search to get the required index

class Solution {
public:
    // recursive modified binary search
    int insertPos(vector<int> &nums, int low, int high, int target){
        //base case with 1 element
        if(low == high){
            if(nums[low] < target){
                return low + 1;
            }else{
                return low;
            }
        }
        //base case with 2 elements
        if(low == high - 1){
            if(nums[high] < target){
                return high + 1;
            }else if(target <= nums[low]){
                return low;
            }else{
                return high;
            }
        }
        //recursive call based on the index 
        int mid = low + ((high - low) >> 1);
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target && nums[mid + 1] > target){
            return mid + 1;
        }else if(nums[mid] > target){
            return insertPos(nums, low, mid - 1, target);
        }else{
            return insertPos(nums, mid + 1, high, target);
        }
    }
    
    int searchInsert(vector<int>& nums, int target) {
        return insertPos(nums, 0, nums.size()-1, target);
    }
};

Approach 2: Use lower_index() method supported by STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), target);
        return (it - nums.begin());
    }
};

Here is the link to the ideone solution : http://ideone.com/TbFRxX

Read More

66. Plus One

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3], the returned vector should be [1, 2, 4] as 123 + 1 = 124.

Approach:

1. Add 1 to the last digit
2. Forward the carry if exists and continue to the beginning

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> plusOne(vector<int>& digits) { int sum, carry = 0, n = digits.size(); //add 1 to the last digit sum = digits[n - 1] + 1; //see if there is a carry generated if(sum > 9){ carry = 1; digits[n - 1] = sum % 10; }else{ //if no carry, add 1 to lsb and return digits[n - 1] = sum; return digits; } //if carry, keep adding till there is no carry for(int i = n - 2; i >= 0; i--){ sum = digits[i] + carry; if(sum > 9){ carry = 1; digits[i] = sum % 10; }else{ //if no carry, return digits[i] = sum; return digits; } } //add 1 to the front if there is carry in the end if(carry){ digits.insert(digits.begin(), 1); } return digits; } };

Here is a link to the ideone solution : http://ideone.com/IbLgNA

Read More

26. Remove Duplicates from Sorted Array

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.

Approach:

1. Copy the current element to the current index if it does not match to the previous element, else move to the next element and repeat the same for all elements of the array.

class Solution {
public:
    
    int removeDuplicates(vector<int>& nums) {
        int numsSize = nums.size();
        if(numsSize <= 1)
            return numsSize;
        
        int j = 1;
        for(int i = 1; i < numsSize; i++){
            if(nums[i] != nums[i - 1]){
                nums[j++] = nums[i];
                j++;
            }
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/T4iddh

Read More

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Approach : Here is the simple recursive solution to solve the problem:

1. Base case : Return one of the lists if another is NULL
2. Else recursively call the function with appropriate values of two current nodes' values

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b) {
    struct ListNode* result = NULL;  
   /* Base cases */  
   if (a == NULL)  
     return(b);  
   else if (b == NULL)  
     return(a);  
   /* Pick either a or b, and recur */  
   if (a->val <= b->val) {  
     result = a;  
     result->next = mergeTwoLists(a->next, b);  
   }else {  
     result = b;  
     result->next = mergeTwoLists(a, b->next);  
   }  
   return(result); 
}

Here is the link to the ideone solution : https://ideone.com/V6zDKA

Read More

27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3] and val = 3, your function should return length = 2, with the first two elements of nums being 2.

Approach: It is a very simple approach where we modify the array on the go by adding only those elements that do not match the target value. 

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int  j = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] != val){
                nums[j++] = nums[i];
            }    
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/SqojbY

Read More

7 Reverse Integer

Problem: Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Approach: Just reverse the number with reversed number stored into a long variable to accommodate overflow if occurred. Return 0 in case of overflow else return the reversed result.

class Solution {
public:
    int reverse(int x) {
        //to accomodate overflowed reversed value if occured
        long revX = 0;
        while (x != 0) {
            revX = revX * 10 + x % 10;
            //overflow check
            if (revX > INT_MAX || revX < INT_MIN) {
                return 0;
            }
            x /= 10;
        }
        return (int) revX;
    }
};

Here is the link to the ideone solution : http://ideone.com/3RwjWu

Read More

88. Merge Sorted Array

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.

Approach : Push the nums1 elements in the end first since no extra space is to be used. Next, use the merge sort merge routine to merge the two sorted arrays. 

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       int i = m, j, k;  
       for(int i = 0; i < m; i++){  
         nums1[m + n - 1 - i] = nums1[m - 1 - i];  
       }  
       i = n; j = 0, k = 0;  
       while(i < m + n && j < n){  
         if(nums1[i] <= nums2[j]){  
           nums1[k++] = nums1[i++];  
         }else{  
           nums1[k++] = nums2[j++];  
         }  
       }  
       while(i < m + n){  
         nums1[k++] = nums1[i++];  
       }  
       while(j < n){  
         nums1[k++] = nums2[j++];  
       }  
    }
};

Read More

9. Palindrome Number

Determine whether a given integer is a palindrome or not. Do this without extra space.

Note that the negative integers are assumed to be non-palindromic. Also, you are not allowed to convert the integer to string, given the restriction of using extra space.

Approach:

Return false if the given integer is negative. Otherwise, reverse the given integer and return true if the reversed integer and the given integer are both same else false.

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        
        int rem, revX = 0;
        int temp = x;
        while(temp > 0){
            rem = temp % 10;
            revX = revX * 10 + rem;
            temp = temp / 10;
        }
        return revX == x;
    }
};

Here is the link to ideone solution : http://ideone.com/9YyJke

Read More