Table of contents
When solving LeetCode problems, especially as a beginner, one of the most critical steps is to understand time complexity. It helps you determine if your solution will work efficiently within the given constraints. This article will guide you step-by-step, using real-life examples, to understand time complexity and how to apply it to solve problems effectively.
What is Time Complexity?
Time complexity describes how the runtime of an algorithm grows as the size of the input increases. It’s measured in Big-O Notation (e.g., 𝑂 ( 1 ) , 𝑂 ( 𝑛 ) , 𝑂 ( 𝑛 2 ) O(1),O(n),O(n square )), which quantifies the efficiency of an algorithm.
Why is Time Complexity Important?
Efficient algorithms are necessary to handle large input sizes.
A slow algorithm can exceed the time limits on platforms like LeetCode, leading to Time Limit Exceeded (TLE) errors.
Understanding time complexity ensures your solution is both correct and scalable.
Example in the image attached-
Key Time Complexities and Their Impacts
Here’s a quick overview of common time complexities and what they mean:
| Time Complexity | Name | Description | When to Use | Example Algorithm | Best Case | Worst Case | Average Case |
| O(1) | Constant Time | Direct operations like indexing | Array access | Array access (nums[0]nums[0]nums[0]) | O(1) | O(1) | O(1) |
| O(log n) | Logarithmic Time | Divide-and-conquer problems | Binary Search | Binary Search | O(1) | O(log n) | O(log n) |
| O(n) | Linear Time | Single pass over data | Finding max/min in an array | Linear search | O(1) | O(n) | O(n) |
| O(n log n) | Linear-Logarithmic | Sorting algorithms | Merge Sort, Quick Sort | Merge Sort | O(n logn) | O(n logn) | O(n logn) |
| O(n^2) | Quadratic Time | Nested loops, small inputs only | Bubble Sort, comparing all pairs | Bubble Sort | O(n) | O(n^2) | O(n^2) |
| O(2^n) | Exponential Time | Combinatorial problems, avoid if possible | Recursive subset generation | Subset generation | O(2^n) | O(2^n) | O(2^n) |
| O(n!) | Factorial Time | Generating permutations, very slow | Traveling Salesman Problem (TSP) | Permutation generation | O(n!) | O(n!) | O(n!) |
How to Determine the Best Time Complexity Based on Constraints
Let’s use an example with the following constraints:
Constraints:
Step-by-Step Analysis
Understand Input Size:
- The input size is up to (100,000). This is large, so you must avoid algorithms with O(n^2) or worse O(2^n) because on the table upper mentionedO(n^2) works on Nested loops, small inputs only
- Aim for O(n) or O(nlogn) solutions for this input size.
Check the Problem Type:
If the problem involves finding duplicates, sorting, or searching, efficient solutions often involve hashing, sorting, or divide-and-conquer techniques.
For example:
Hashing with O(n) is suitable for problems like "Contains Duplicate."
Sorting with O(nlogn) works well for range queries or frequency-based problems.
Assess Constraints on Values:
The range of numbers which is second one from -1billion to +1 billion is large, but this doesn’t directly affect time complexity.
Instead, it influences memory usage. For example:
Using a frequency array for this range is infeasible .
Use a HashSet or HashMap, which scales efficiently.
Pick the Right Algorithm:
Based on input size and problem type:
- Avoid brute-force as it will result in TLE.
How to Choose the Best Approach for a New Problem
Follow these steps:
Read the Constraints Carefully:
Understand the Problem Type:
Think of Edge Cases:
Example: An array of size 1
Large inputs need efficient solutions.
Plan Your Solution:
Start with a brute-force approach to understand the logic.
Optimize it based on constraints.
Beginner-Friendly Real-Life Analogies
O(1) (Constant Time):
- Like checking a specific page in a book — it doesn’t matter how big the book is.
O(n) (Linear Time):
- Reading every page in a book — the more pages, the longer it takes.
O(n^2) (Quadratic Time):
- Comparing every student in a class to every other student — grows exponentially with class size.
O(log n) (Logarithmic Time):
- Searching for a word in a dictionary — halve the search space at each step.
Summary of Time Complexities
| Time Complexity | Efficient For | Avoid If |
| O(1) | Constant-time operations | Rarely an issue |
| O(logn) | Divide-and-conquer problems | Inputs that don’t reduce recursively |
| O(n) | Single-pass problems | Very large inputs with nested operations |
| O(nlogn) | Sorting and partitioning problems | Only works for n≥105n \geq 10^5n≥105 |
| O(n2) | Small inputs (n≤1000n \leq 1000n≤1000) | Large inputs |
| O(2n) | Combinatorial problems | Large nnn (e.g., n>20n > 20n>20) |
Key Takeaways for Beginners
Always read the constraints to determine the required time complexity.
Start simple: Understand brute-force solutions, then optimize.
By following these steps, you'll confidently approach time complexity and solve LeetCode problems like a pro! 🚀