Author Arunima Mandal

Removing Nth Node From End of List

Arunima Mandal Leave a comment

Problem Statement: Given the head, remove the N-th node from the end of the list and return the head.

Note: The idea is pretty intuitive. We must iterate through the list starting from the head to know the size of the linked list. Knowing the size, we can iterate up to the node before the nth node. That way we can easily point towards the next node of the previous node of the “to-be-removed” node.

The only exception case is if we have to remove the head node. We just have to assign the head node to the next node of the head node.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *node=head;
        int sz=0;
        while(node)
        {
          node=node->next;
          sz++;
        }
        if(sz==n) //head to be deleted
        {
            ListNode *temp=head;
            head=head->next;
            delete temp;
            return head;
        }
        int i=0;
        node=head;
        int target=sz-n-1;
        while(i<target)
        {
          node=node->next;
          i++; 
        }
        ListNode *temp=node->next;
        node->next=node->next->next;
        delete temp;
        return head;
    }
};

LeetCode 388. Longest Absolute File Path

Arunima Mandal 1 Comment

Problem Link: https://leetcode.com/problems/longest-absolute-file-path/

Note:
This problem intuitively resembles a tree structure. But it can be solved using a deque easily, though I think the first data structure that will come to mind is a stack, at least that was in my case. A stack would work, but eventually while accessing all the elements of the stack for length counting, then you will get how deque will serve in that case!

In the following code, one limiting criterion is that the length of the level cannot be less than the size of the deque, if it is greater then we have already processed the subdirectory/file and we haven’t found our answer yet, so we can discard that from the deque. 

class Solution {
public:
    int lengthLongestPath(string input) {
        deque<int> dq;
        int len=0, level=0, res=0;
        bool flag=0;
        for(int i=0; i<input.size(); i++)
        {
            if(input[i]=='\n')
            {
                dq.push_back(len);
                len=0;
                level=0;
                flag=0; 
            }
            else if(input[i]=='\t') level++;
            else if(input[i]=='.')
            {
                flag=1;
                len++;
            }
            else
            {
                len++;
                if(flag)
                {
                    int sum=0;
                    for(int i=0; i<dq.size(); i++)
                    {
                        sum+=dq[i];
                    }
                    res=max(res, sum+len+level);
                }
                while(level<dq.size()) dq.pop_back();
            }
        }
        return res;
    }
};

SPOJ – DIGOKEYS – Find the Treasure

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/DIGOKEYS/

Note: This problem is pretty much a simple Graph problem. I have solved this using BFS. One thing that I was confused about was how to handle the “lexicographically smallest order of path“. But after writing the basic code, the idea that came to my mind is how about if I sort the initial graph while building that by inserting the edge nodes. If the edges are sorted, then while running the BFS, it will automatically choose the smallest numbers first! That solves our finding of “lexicographically smallest order of path”. Please feel free to comment below if you have any other ideas to implement this.

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
int parent[MAX];

void path_print(int dst, int ans)
{
    vector<int> path;
    dst=parent[dst]; //As the question suggests not to include the last destination which is obvious in every case
    while(dst!=-1)
    {
        path.push_back(dst);
        dst=parent[dst];
    }
    cout<<path[ans-1];
    for(int i=ans-2; i>=0; i--) cout<<" "<<path[i];
    cout<<endl;
}


int bfs(int src, int dst, vector<vector<int> > &g)
{
    int vis[MAX]={0};
    int dis[MAX];
    vis[src]=1;
    dis[src]=0;
    parent[MAX]={-1};
    parent[src]=-1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==dst) return dis[u];
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+1;
                parent[v]=u;
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<vector<int> > g(MAX, vector<int> (11));
        for(int j=1; j<n; j++)
        {
            int edge;
            cin>>edge;
            int src=j;
            vector<int> des; //for sorting the edges// for "lexicographical" purpose
            for(int k=0; k<edge; k++)
            {
                int dst;
                cin>>dst;
                des.push_back(dst);
            }
            sort(des.begin(), des.end()); //We are doing this only to ensure the "lexicographically smallest" order of path
            for(int k=0; k<des.size(); k++)
            {
                g[src].push_back(des[k]);
            }

        }
        int ans=bfs(1,n, g);
        cout<<ans<<endl;
        if(ans!=-1)
        {
            path_print(n, ans);
        }
        cout<<endl;
    }
    return 0;
}

Longest Consecutive Sequence

Arunima Mandal Leave a comment

Problem Statement: https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Notice that, the repeated numbers do not count! Also, note that here the ‘sequence’ does not mean that they cannot break! But for many problems with “sequence”, that is not the case. So it’s better if you can verify this with the problem creator before attempting to solve the question.

Approach 1: This problem can be solved in different ways. The brute force one would take O(N^3). I am not going to show that here, because honestly, I think that solution didn’t come to mind at all! I think except for newbies, for most programmers that is the case.

Approach 2: The first solution that comes intuitively to mind is to sort the array first! That simplifies the solution instantly! But that would take O(NlogN) time because sorting alone takes that time, the rest of the method would take O(N) time understandably. So the overall time complexity will be O(NlogN) ultimately.

Approach 3: Other O(NlogN) solutions are using set or ordered_map. Since here the sequence of the original array doesn’t matter, and also, the repeated numbers do not matter, so we can use a set and map, where looking up the elements takes O(logN) time! Both in set or map, the numbers are always sorted when constructed. So the overall time complexity of the solution would take O(NlogN) time.

Approach 4: We can improve the time complexity to O(N) if we can think slightly out of the box. The method is to use a hash set or hash map and then run an intelligent sequence building method. Here basically, we will search for the elements that have no precedent number. If found, then we’ll only process that number to find its later consecutive numbers. Since we’ll not deal with the numbers that have precedent numbers, so we are essentially avoiding N^2 computation. In the following code below, in worst case, it will take N+N time, resulting in O(N+N)=O(2N)=O(N) time complexity

Code:

#include <bits/stdc++.h>

using namespace std;

int longestConsecutive_sorting(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    sort(nums.begin(),nums.end());
    int maxi=-1,count=1;
    for(int i=1; i<nums.size(); i++)
    {
        if(nums[i]-nums[i-1]==1) count++;
        else if(nums[i]-nums[i-1]!=0)
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_set(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    set<int> st;
    for(int i=0; i<nums.size(); i++) st.insert(nums[i]);
    set<int>:: iterator it;
    int maxi=-1,count=1;
    for(it=st.begin(); next(it)!=st.end(); ++it)
    {
        int x=*it;
        int y=*(next(it));
        if(y-x==1) count++;
        else
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_map(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    map<int,int> mp;
    for(int i=0; i<nums.size(); i++) mp[nums[i]]++;
    map<int,int>:: iterator it;
    int maxi=-1,count=1;
    for(it=mp.begin(); next(it)!=mp.end(); ++it)
    {
        int x=it->first;
        int y=(next(it))->first;
        if(y-x==1) count++;
        else
        {
            maxi=max(count,maxi);
            count=1;
        }
    }
    return max(count,maxi);
}

int longestConsecutive_hashSet(vector<int>& nums)
{
    if(nums.size()==0) return 0;
    unordered_set<int> st;
    for(int i=0; i<nums.size(); i++) st.insert(nums[i]);
    unordered_set<int>:: iterator it;
    int ans=0;
    for(it=st.begin(); it!=st.end(); ++it)
    {
        if(!st.count((*it)-1))
        {
            int cur=*it;
            int count=1;
            while(st.count(cur+1))
            {
                cur++;
                count++;
            }
            ans=max(ans,count);
        }
    }
    return ans;
}

int main()
{
    vector<int> nums;
    cout<<"No. of elements"<<endl;
    int n;
    cin>>n;
    cout<<"Enter an unsorted array elements: "<<endl;
    for(int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        nums.push_back(x);
    }
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Sorting is "<<longestConsecutive_sorting(nums)<<endl;
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Set is "<<longestConsecutive_set(nums)<<endl;
    //Takes O(NlogN) time
    cout<<"Longest Consecutive sequence using Map is "<<longestConsecutive_map(nums)<<endl;
    //Takes O(N) time
    cout<<"Longest Consecutive sequence using hashSet is "<<longestConsecutive_hashSet(nums)<<endl;
    return 0;
}

Number of subarrays having a sum exactly equal to k

Arunima Mandal Leave a comment

Note:

This problem states that – Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

Brute force method: It comes to the mind easily. Time complexity is O(n^2) and space complexity is O(1). So in most cases, this solution would exceed the time limit.

int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            int total=0;
            for(int j=i; j<nums.size(); j++)
            {
                total+=nums[j];
                if(total==k) ans++;
            }
        }
        return ans;    
    }

Cumulative /Prefix Sum:

Though this thing doesn’t come to mind at first, this way is the more efficient one. The main trick is we have to keep the cumulative sum in an array first, then we’ll have to work on that array. The first idea is that to know the sum of any subarray in the range [i,j], the equation would be: sum=a[j]-a[i-1] (assuming a is the cumulative sum array). Since our sum has to be k, so we can write, k=a[j]-a[i-1]. Alternatively, we can write, a[i-1]=a[j]-k. Now we will have to run a loop for each j, to see whether there is any prefix sum equal to a[i-1] till now. We’ll check that with the help of a hashmap. If our condition is satisfied, we increase our answer variable by the count in the hashmap.

Time complexity: O(N)
Space complexity: O(N); for the hashmap.

int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> ump;
        ump[0]=1;
        int a[20004]={0};
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            if(i==0) a[i]=nums[i];
            else a[i]=a[i-1]+nums[i];
            
            int x=a[i]-k;
            if(ump.count(x)) ans+=ump[x];
            ump[a[i]]++;
        }
        return ans;    
    }