Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Problem link

Solution

  • the random pointer may point to a node that hasn’t been created yet
  • create the linked list first, and then add random pointers in the second pass using hashtable constant-time lookup
  • need two passes
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // two lookups: ori.cur ->(using pointer) ori.rand -> new.rand
        unordered_map<RandomListNode*, RandomListNode*> h;
        RandomListNode* dummy = new RandomListNode(0);
        RandomListNode* cur = head;
        RandomListNode* new_cur = dummy;
        // linking next pointers
        while (cur){
            new_cur->next = new RandomListNode(cur->label);
            h[cur] = new_cur->next;
            cur = cur->next;
            new_cur = new_cur->next;
        }
        new_cur->next = NULL;
        // linking random pointers
        cur = head;
        new_cur = dummy->next;
        while (cur){
            new_cur->random = cur->random? h[cur->random]:NULL;
            new_cur = new_cur->next;
            cur = cur->next;
        }
        new_cur = dummy->next;
        delete(dummy);
        return new_cur;
    }
};
Advertisements
Copy List with Random Pointer

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Problem link

Solution

  • use hash table to reduce the problem into finding longest subsequence using DP
  • Memory Limit Exceeded due to the extra memory use
class Solution
{
public:
    int minDistance(string word1, string word2) {
        if (word1.empty()) return word2.size();
        if (word2.empty()) return word1.size();
        unordered_map<char, queue<int>> m;
        int i;
        unordered_map<char, queue<int>>::const_iterator got;
        // when there are duplicates, there are ordered increasingly in the map
        for (i=0; i<word1.size(); ++i) {
            got = m.find(word1[i]);
            if (got == m.end()) {
                queue<int> q;
                q.push(i);
                m[word1[i]] = q;
            } else {
                m[word1[i]].push(i);
            }
        }
        vector<pair<int, int>> idx; // need to store both here
        // whenever there is a found, delete the key in the hashmap
        for (i=0; i<word2.size(); ++i) {
            got = m.find(word2[i]);
            if (got != m.end()) {
                idx.push_back(make_pair(m[word2[i]].front(), i));
                m[word2[i]].pop();
                if ((got->second).empty()) {
                    m.erase(got);
                }
            }
        }
        if (idx.empty()) return max(word1.size(), word2.size());

        // find all longest increasing subsequence in idx, which can be sovled by DP
        // l[i] = max(l[j])+1 for idx[j]<idx[i]
        // 2D DP using 1D array
        vector<int> l(idx.size(), 1);
        // store the indices of idx.first
        // 1 dimension: corresponses to each element in idx
        // 2 & 3 dimensions: there can be multiple longest sequences related to each element
        vector<vector<vector<int>>> vvv (idx.size(),vector<vector<int>>());
        int j;
        int maxl;
        vector<int> maxidx;
        for (i=0; i<idx.size(); ++i) {
            maxl = i>0 ? l[i-1]:1; // inherent previous longest sequence
            for (j=0; j<i; ++j) {
                // be careful about the case where longest increasing subsequence is 1
                if (idx[j].first<idx[i].first) {
                    if (l[j]+1>maxl) {
                        maxl = l[j]+1;
                        maxidx.clear();
                        maxidx.push_back(j);
                        // printf("better: maxidx push j %d\n", j);
                    } else if (l[j]+1==maxl) {
                        maxidx.push_back(j);
                        // printf("equal: maxidx push j %d\n", j);
                    }
                }
            }
            l[i] = maxl;
            // add each to each sequence in vv, add i at the end of each sequence
            if (!maxidx.empty()){
                // printf("maxidx not empty\n");
                for (j=0; j<maxidx.size(); ++j){
                    for (int k=0; k<vvv[j].size(); ++k){
                        vvv[i].push_back(vvv[j][k]);
                        vvv[i].back().push_back(i); // add the last element
                    }
                }
            }else{
                vector<vector<int>> vv;
                vector<int> v;
                v.push_back(i);
                vv.push_back(v);
                vvv[i] = vv;
            }
        }
        vector<vector<int>> vv = vvv.back();
        // find minimal edit distance from all longest subsequence
        int I;
        int preI;
        int minE = INT_MAX;
        int dist;
        for (i=0; i<vv.size(); ++i) {
            dist = 0;
            for (j=0; j<vv[0].size(); ++j) {
                I = vv[i][j];
                if (j==0) {
                    dist += max(idx[I].first, idx[I].second);
                } else if (0<j && j<vv[0].size()) { // inbetween
                    preI = vv[i][j-1];
                    dist += max(idx[I].first-idx[preI].first-1, idx[I].second-idx[I].second-1);
                }
            }
            dist += max(word1.size()-idx.back().first-1, word2.size()-idx.back().second-1);
            minE = min(dist, minE);
        }
        return minE;
    }

};

Direct DP solution

  • applying the DP directly to the strings
  • problem: how to find matching initially?
  • it is quite similar to the longest common subsequence problem (LCS), rather than LCS, here we store the edit distance up to word1[i] and word2[j] at [i][j]
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1));
        // first row
        for (int i=0; i<=word1.size(); ++i){
            dp[i][0] = i;
        }
        // first column
        for (int i=1; i<=word2.size(); ++i){
            dp[0][i] = i;
        }
        for (int i=1; i<=word1.size(); ++i){
            for (int j=1; j<=word2.size(); ++j){
                dp[i][j] = dp[i-1][j-1];
                if (word1[i-1]!=word2[j-1]){
                    ++dp[i][j];
                    dp[i][j] = min(min(dp[i][j-1]+1, dp[i][j]), dp[i-1][j]+1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
Edit Distance

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Problem link

Solution

  • use hash table to cache elements visited
  • runtime complexity: O(n)
  • space complexity: O(n)
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        unordered_map<int, int> h;
        unordered_map<int,int>::const_iterator found;
        vector<int> ret;
        for (int i=0; i<numbers.size(); ++i){
            found = h.find(target-numbers[i]);
            if (found!=h.end()){
                if (found->second<i+1){
                    ret.push_back(found->second);
                    ret.push_back(i+1);
                }else{
                    ret.push_back(i+1);
                    ret.push_back(found->second);
                }
                break;
            }
            h[numbers[i]] = i+1;
        }
        return ret;
    }
};

Two pointer solution

  • sort the array first, design a struct to pair elements and their indices
  • runtime complexity: O(n log n)
  • space complexity: O(n)
class Solution {
class elem{//nested class
public:
    int val;
    int idx;
    // constructor and concise way to assign
    elem(int v, int i):val(v), idx(i) {}
    // operation overload
    bool operator<(elem e) const {
            return val<e.val;
    }
};
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> res(2,-1);
        vector<elem> arr;
        // array of elem objects
        for(int i=0; i<numbers.size(); i++) 
            arr.push_back(elem(numbers[i],i));
        sort(arr.begin(),arr.end());
        
        int left = 0, right = arr.size()-1; // init two pointer
        while(left<right) {
            if(arr[left].val+arr[right].val==target) {
                res[0] = min(arr[left].idx,arr[right].idx)+1;
                res[1] = max(arr[left].idx,arr[right].idx)+1;
                break;
            }
            else if(arr[left].val+arr[right].val<target) 
                left++;
            else
                right--;
        }
        return res;
    }
};
Two Sum

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Problem link

Solution

  • achieving O(n) runtime complexity typically requires hash table
  • every time an element is visited, check for its neighbors in natural number sequence, however, it is still a quadratic algorithm, \sum_{i=1}^n n = O(n^2)
  • time limit exceeded on OJ
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, int> h;
        int i;
        int maxC = 0;
        int inter;
        int count=0;
        unordered_map<int,int>::const_iterator found; 
        for (i=0; i<num.size(); ++i){
            h[num[i]] = i;
        }
        // avoid visiting the same element
        vector<bool> visited(num.size(), false); 
        for (i=0; i<num.size(); ++i){
            if (!visited[i]){
                inter = 1;
                count = 1;
                // checks backforward
                while ( (found=h.find(num[i]-inter))!=h.end()){
                    visited[found->second]=true;
                    inter++;
                }
                count += inter;
                // check forward
                inter = 1;
                while ( (found=h.find(num[i]+inter))!=h.end()){
                    visited[found->second]=true;
                    inter++;
                }
                count += inter;
                maxC = max(maxC, count);
            }
        }
        return maxC;
    }
};

An improved solution

  • using undeorded_set instead, since we don’t need pairs
  • erase visited elements in the set, this way we don’t even need the visited flag array
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> h;
        int i;
        int maxC = 0;
        int inter;
        int count=0;
        unordered_set<int>::const_iterator found; 
        for (i=0; i<num.size(); ++i){
            h.insert(num[i]);
        }
        // avoid visiting the same element
        for (i=0; i<num.size(); ++i){
                count = 0;
                inter = 0;
                // checks backforward
                while ( (found=h.find(num[i]-inter))!=h.end()){
                    h.erase(found);
                    inter++;
                    count++;
                }
                // check forward
                inter = 1;
                while ( (found=h.find(num[i]+inter))!=h.end()){
                    h.erase(found);
                    inter++;
                    count++;
                }
                maxC = max(maxC, count);
        }
        return maxC;
    }
};
Longest Consecutive Sequence