class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> hm = new HashMap<>();
for (int i=0; i<nums.length; i++) {
hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
}
for (int key : hm.keySet()) {
if (hm.get(key) == 1)
return key;
}
return -1;
}
}As always you can track my recent-most submissions on my leetcode page: https://leetcode.com/chandniverma/Feel free to share your thoughts in comments.
Two things mam.
ReplyDeleteFirst iterating through hashmap i.e. O(n/3) roughly O(n) when n is large
And then inside using hm.get() which is again O(n/3) complexity.
Hence on upper level O(n^2).
And also using hashmap compromises the extra memory constraint.
FYI, all hash operations are O(1) provided the hash distributes its elements uniformly across buckets and the default implementation does it for large values of n.
DeleteAlso, there is no such thing as O(n/3). It's only O(n) as we drop all constant multipliers.
Lastly, in my posted solution both the for loops are O(n) and O(n) + O(n) is O(n) only (again, as multipliers in complexity are ineffective essentially).
Hope this helps!
That extra memory constraint was a followup not a hard requirement as the solution passes the problem judge!
DeleteYou can simplify this considerably without resorting to hashmap by using TreeSets. Code at https://onlinegdb.com/SkRB2iA3U
ReplyDeleteIf we store the elements in a treeset, they will be O(n lg n) as TreeSet guarantees O(lg n) time in the worst case for element insertion. That will be a bottleneck operation slowing down the algorithm even further down to O(n lg n) from current O(n)!
Delete