Read Constraints the Right Way
Alim Mohammad
Posted on October 31, 2022
In case you've found it rigid to observe what approach should be the optimal or how to get rid of the annoying time limit error, reading constraints in an important step towards a better approach for problem solving.
N denotes the number of operations for a range.
N == 10^5 - One of the most sought-after constraints in competitive programming and interviews and a boundary line solution to your code in the front of the interviewer. The Time Complexity encompassing under it are O(N), O(N*logN(base2)) and O(N*root(N))
N == 10^6 - The increment of a single power will bar the later one to keep only O(N) and O(N*logN(base2)) enclosed.
N >= 10^9 - The one supportive complexity at this point is O(logN) with all the other failing at such an insurmountable number of operations. Binary Search much?.
N == 10^3 - Apart from O(N), it extends its support to O(N^2) and O(N^2 * logN) solutions. This one is a Breath of fresh air to the beginners.
N == 10^2 - The cubic computations are allowed in this special case. Going the brute force might not be a sign of concern in this case. You can opt for O(N), O(N^2), O(N^3) and O(N^3*logN) solutions beforehand.
N <= 20 - Exponential complexity is accepted in this constraint with recursion and backtracking the goto approach for solving such problems.
Problem Categorization
If at an interview, the constraints can give you the hints on which method would be most suitable for to solve your problem at a single go: -
1. 10^2 - Brute force/ Greedy
2. 10^5 - Sorting/ Combinations on Binary Search
3. 10^8 - HashMap/ Sliding Window/Two Pointer/Stack/Queue
4. 10^10 - Binary Search
5. 4-20 - Recursion/Backtracking
As obvious, all of them are going to support O(1) in case you are wizard enough at an interview. Hope this helps you with interview. Grind Hard till You Make It.
Posted on October 31, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.