Pascal's Triangle

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

Solution:
class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > sol;
        vector<int> prev, curr;
        
        if (numRows == 0)
            return sol;
        
        // base;
        prev.push_back(1);
        sol.push_back(prev);
        
        for (int i = 0; i < numRows - 1; i++) {
            curr.push_back(1);
            int prev_size = prev.size();
            for (int prev_iter = 0; prev_iter < (prev_size - 1); prev_iter++) {
                curr.push_back(prev[prev_iter] + prev[prev_iter + 1]);
            }
            curr.push_back(1);
            sol.push_back(curr);
            // make prev ready for next iteration.
            prev = curr;
            curr.clear();
        }
        return sol;
    }
};

======= Online one =======

class Solution {

public:

    vector<vector<int> > generate(int numRows) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        vector<vector<int> > res;

        if (numRows==0){return res;}

        vector<int> r;

        r.push_back(1);

        res.push_back(r);

        if (numRows==1){return res;}

        r.push_back(1);

        res.push_back(r);

        if (numRows==2){return res;}

         

        for (int i=2;i<numRows;i++){

            vector<int> c(i+1,1);

            for (int j=1;j<i;j++){

                c[j]= res[i-1][j]+res[i-1][j-1];

            }

            res.push_back(c);

        }

        return res;

    }

};

Pascal Triangle 2

Problem:

Given an index k, return the k^th row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Solution:
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> helper_prev, helper_curr;
        
        // Base case.
        helper_prev.push_back(1);
        
        for (int i = 0; i < rowIndex; i++) {
            helper_curr.push_back(1);
            int size = helper_prev.size();
            for (int prev_iter = 0; prev_iter < (size - 1); prev_iter++) {
                helper_curr.push_back(helper_prev[prev_iter] + helper_prev[prev_iter+1]);
            }
            helper_curr.push_back(1);
            helper_prev = helper_curr;
            // make helper_curr blank
            helper_curr.clear();
        }
        return helper_prev;
    }
};

Valid Palindrome

problem:

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.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

solution:
class Solution {
public:
    // instead use isalnum() function. 
    bool valid(char a) {
        if ((a >= 'A' && a <= 'Z') ||
            (a >= 'a' && a <= 'z') ||
            (a >= '0' && a <= '9'))
            return true;
        return false;
    }
    
    bool equal (char a, char b) {
        if (tolower(a) == tolower(b))
            return true;
        return false;
    }
    
    bool isPalindrome(string s) {
        int size = s.size();
        int start = 0, end = size - 1;
        while (start < end) {
            while (!valid(s[start]) && start < end)
                start++;
            while (!valid(s[end]) && start < end)
                end--;
            if (!equal(s[start++], s[end--]))
                return false;
        }
        return true;
    }
};

============
Shorter one: ( isalnum() and tolower() helper function in c++ )

bool isPalindrome(string s) {
        int size = s.size();
        int start = 0, end = size - 1;
        while (start < end) {
            while (!isalnum(s[start]) && start < end)
                start++;
            while (!isalnum(s[end]) && start < end)
                end--;
            if (tolower(s[start++]) != tolower(s[end--]))
                return false;
        }
        return true;
    }

==== Third one ======

    bool isPalindrome(string s) {
        bool ans = false;
        if (s.size() == 0) {
            return true;
        }
       
        int left = 0, right = s.size() - 1;
        while (left <= right) {
            while(!isalnum(s[left])) {
                left++;            
            }
            while(!isalnum(s[right])) {
                right--;
            }

            if (left >= right) {
                return true;
            } else if(tolower(s[left++]) != tolower(s[right--])) {
                return false;
            }
        }
        return true;
    }

Min Stack

Problem:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution:
class MinStack {
private:
    stack<int> istack;
    stack<int> min_stack; // Creating an equal size additional stack. Could be done by just storing minimum element once.
public:
    void push(int x) {
        if (min_stack.empty() || x <= min_stack.top()) {
            min_stack.push(x);
        } else {
            min_stack.push(min_stack.top());
        }
        istack.push(x);
    }

    void pop() {
        if (!istack.empty()) {
            istack.pop();
            min_stack.pop();
        }
    }

    int top() {
        int elem;
        if (!istack.empty()) {
            elem = istack.top();
        }
        return elem;
    }

    int getMin() {
        int elem;
        if (!min_stack.empty()) {
            elem = min_stack.top();
        }
        return elem;
    }
};

Intersection of Two Linked Lists

Problem:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    int length (ListNode *head) {
        int result = 0;
        while (head != NULL) {
            head = head -> next;
            result++;
        }
        return result;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *temp1, *temp2;
        int listALength = length(headA);
        int listBLength = length(headB);
        
        int bigger, smaller;
        
        if (listALength > listBLength) {
            temp1 = headA;
            temp2 = headB;
            bigger = listALength;
            smaller = listBLength;
        } else {
            temp1 = headB;
            temp2 = headA;
            bigger = listBLength;
            smaller = listALength;
        }
        
        for (int i = bigger; i > smaller; i--) {
            temp1 = temp1->next;
        }
        
        while (temp1 != NULL || temp2 != NULL) {
            if (temp1 == temp2)
                return temp1;
            else {
                temp1 = temp1 -> next;
                temp2 = temp2 -> next;
            }
        }
        return NULL;
    }
};