Why does using unordered map over a vector give me a TLE?

Question

I am solving this question on leetcode link

This is my working solution using an unordered map which gives me a TLE while using a vector of vectors passes all test cases.
They both work on the same logic then why does using an unordered map give me a TLE ?

class Solution {
public:
    int longestArithSeqLength(vector<int>& a) {
        
        // vector of umaps
        vector<unordered_map<int, int>> aux(a.size());
        // iterate array
        int n = a.size();
        int ans = INT_MIN;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                int currdiff = a[j] - a[i];
                unordered_map<int, int> &umapj = aux[j];
                unordered_map<int, int> &umapi = aux[i];
                
                umapi[currdiff] = umapj[currdiff] + 1;
                
                if(umapi[currdiff] > ans)
                {
                    ans = umapi[currdiff];
                }
            }
        }
        return ans+1;
    }
};

code using vector:

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int> (1005, 1));
        int maxLen = 1;
        
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                int d = A[j] - A[i];
                dp[i][d + 500] = dp[j][d + 500] + 1;
                maxLen = max(maxLen, dp[i][d + 500]);
            }
        }
        return maxLen;
    }
};

score 1 · Accepted Answer · answered Dec 24 '20 at 12:24

Top answer from Why is vector faster than unordered_map?

First thing to note is, although the average time to query an unordered_map is constant, the worst case is not O(1). As you can see here it actually rises to the order of O(N), N denoting the size of the container.

Secondly, as vector allocates sequential portions of memory, accessing to that memory is highly efficient and actually is constant, even in the worst-case. (i.e. simple pointer arithmetic, as opposed to computing the result of a more complex hash function) There is also the possibility of various levels of caching of sequential memory that may be involved (i.e. depending on the platform your code is running on) which may make the execution of a code using vector even faster, compared to one that is using unordered_map.

In essence, in terms of complexity, the worst-case performance of a vector is more efficient than that of unordered_map. On top of that, most hardware systems offer features such as caching which give usage of vector an even bigger edge. (i.e. lesser constant factors in O(1) operations)

Why does using unordered map over a vector give me a TLE?

1 Answers1