1

This code works time efficiently but if I replace the two lines with comment lines (assigning value to A and B), it takes much more time to pass certain test cases. constraints: n,m in range(10^5), any integer in arr is in range(10^9) Please explain.

n, m = input().split()
arr=list(map(int,input().split()))
A = set(map(int,input().split()))  #list(map(int,input().split()))
B = set(map(int,input().split()))  #list(map(int,input().split()))
count=0
for i in range(len(arr)):
    if arr[i] in A:
        count+=1
    elif arr[i] in B:
        count+=-1
print(count)
Gahan
  • 4,075
  • 4
  • 24
  • 44
Shobhit Singhal
  • 11
  • 1
  • 1
    Testing for membership in a list is `O(n)` where `n` is the length of a list. Testing for membership in a set is essentially `O(1)`. In the case of a list, it searches each list element one a a time. In the case of a set, it's doing a hash lookup. – Tom Karzes Dec 19 '17 at 06:58
  • first read this thread [list vs set](https://stackoverflow.com/questions/12354515/what-is-the-difference-between-sets-and-lists-in-python) ; secondly why are you using same statement `map(int,input().split())` for thrice? also read about [TimeComplexity](https://wiki.python.org/moin/TimeComplexity) of operations in python. – Gahan Dec 19 '17 at 06:58

1 Answers1

0

Look up time in a list is O(N) and look up time in set is O(1).

To check if an element is contained in a list every element of a list has to be checked until either an element is found or not. This gives look up time proportional to size of the list or O(N). set is implemented as a hashtable which much more efficient, and look up time is on average O(1), or look up time does not increase much as size of set increases.

Akavall
  • 82,592
  • 51
  • 207
  • 251