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

Reverse String

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

1 2 3 4 5 6 7 8 9 10 11

string reverseString(string &s) { int low = 0, high = s.length() - 1; while(low < high){ char t = s[low]; s[low] = s[high]; s[high] = t; low++; high--; } return s; }

Read More

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach:  The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

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

char* reverseVowels(char* s) { int low = 0, high = strlen(s) - 1; char c; while(low < high){ //move forward to skip consonant while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){ low++; } //move backward to skip consonant while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){ high--; } if(low < high){ c = s[low]; s[low] = s[high]; s[high] = c; low++; high--; } } return s; }

Read More

Move Zeros

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void moveZeroes(int* nums, int numsSize){ int i = 0, j = 0; for(i = 0; i < numsSize; i++){ //copy non-zero elements if(nums[i] != 0){ nums[j] = nums[i]; j++; } } //put zeros in the end while(j < numsSize){ nums[j++] = 0; } }

Read More

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Approach: Use binary search.

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

int peakIndex(int *arr, int low, int high){ if(low == high){ return low; } if(low + 1 == high){ if(arr[low] >= arr[high]){ return low; }else{ return high; } } int mid = (low + high) / 2; if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){ return mid; }else if(arr[mid] < arr[mid - 1]){ //peak lies on the left since arr[mid - 1] > arr[mid] && arr[0] = -infinity so there has to be an element which is peak on the left return peakIndex(arr, low, mid - 1); }else{ //peak lies on the right return peakIndex(arr, mid + 1, high); } } int findPeakElement(int* nums, int numsSize) { return peakIndex(nums, 0, numsSize - 1); }

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

13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Approach:

According to an answer taken from here[1]:

• A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 3 (three units). To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.  
• The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "V", "L", and "D" can never be repeated. 
• "I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.
• Only one small-value symbol may be subtracted from any large-value symbol.

Here is the code for the same:

class Solution {
public:
    int romanToInt(string s) {
        map<char, int> m;
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        int len = s.length();
        if(len <= 0)
            return 0;
        int result = m[s[len - 1]];
        for(int i = len - 2; i >= 0; i--){
            if(m[s[i]] < m[s[i+1]]){
                result = result - m[s[i]];
            }else{
                result = result + m[s[i]];
            }
        }
        return result;
    }
};

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

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

20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Approach: The idea is to use Stack and implement the following algorithm:

1. if the current character is an opening bracket (of any type), push it to the stack and continue with the next character
2. else if the current character is a closing bracket, following cases apply:
1. if stack is empty - return error and exit
2. else if the current character and the stack top forms matching parenthesis i.e. opening and closing brackets are of same type, pop the stack top and continue with the next character otherwise return error and exit
3. Return error if the stack is not empty after all the characters are exhausted otherwise successful

class Solution {
public:
    
    int isMatching(stack<char> &stk, char c){
        if(stk.empty()){
            return 0;
        }
        char topC = stk.top();
        if( (topC == '(' && c == ')') || (topC == '{' && c == '}') || (topC == '[' && c == ']') )
            return 1;
        return 0;
    }
    
    bool isValid(string s) {
        stack<char> stk;
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                    stk.push(s[i]);
                    continue;
            } else if((s[i] == ')' || s[i] == '}' || s[i] == ']') && isMatching(stk, s[i])){
                stk.pop();
                continue;
            }
            return false;
        }
        if(!stk.empty())
            return false;
        return true;
    }
};

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

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