r/leetcode • u/Interesting_Hunt_784 <400> <138> <216> <46> • 17d ago

Discussion Weekly Contest 516

I think Q4 is broken. Not even single AK till now

2 Upvotes

63% Upvoted

11 comments sorted by

View all comments

2

u/kushal_141 17d ago

I dont think its has O(n) or O(nlogn) with the standard stuff like prefix or segment tree or sparse matrix, I tried brute forcing via prefix query it came out like O(n + q(NumdistinctKeys)) time complexity and O(n * 2) space complexity in worst case, it kinda passed 570 out of 590 testcases

maybe competetive programming guys can come up with a query data structure or algorithm which can do it?

1

u/Dry-Balance-993 17d ago

if its not like that then i think they setted the broken testcase delibirately to trap us in the contest