Time Complexity

class Solution { public: int maxSubArray(vector& nums) { int n = size(nums), ans = INT_MIN; for(int i = 0; i < n; i++) for(int j = i, curSum = 0; j < n ; j++) curSum += nums[j], ans = max(ans, curSum); return ans; } };

• O(n)

• O(n²)

• O(n log n)

• O(1)

class Solution { public: vector spiralOrder(vector>& matrix) { vectorv; int r1=0,r2=matrix.size()-1,c1=0,c2=matrix[0].size()-1; while(r1<=r2&&c1<=c2){ for(int i=c1;i<=c2;i++){ v.push_back(matrix[r1][i]); } r1++; if(r1>r2) break; for(int i=r1;i<=r2;i++){ v.push_back(matrix[i][c2]); } c2--; if(c1>c2) break; for(int i=c2;i>=c1;i--){ v.push_back(matrix[r2][i]); } r2--; if(r1>r2) break; for(int i=r2;i>=r1;i--){ v.push_back(matrix[i][c1]); } c1++; } return v; } };

• O(n²)

• O(m × n)

• O(log n)

• O(n)

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: merged = [] intervals.sort(key=lambda x: x[0]) prev = intervals[0] for interval in intervals[1:]: if interval[0] <= prev[1]: prev[1] = max(prev[1], interval[1]) else: merged.append(prev) prev = interval merged.append(prev) return merged

• O(n²)

• O(n)

• O(n log n)

• O(log n)

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: if not obstacleGrid or obstacleGrid[0][0] == 1: return 0 rows, cols = len(obstacleGrid), len(obstacleGrid[0]) dp = [0] * cols dp[0] = 1 for r in range(rows): for c in range(cols): if obstacleGrid[r][c] == 1: dp[c] = 0 else: if c > 0: dp[c] += dp[c - 1] return dp[cols - 1]

• O(n)

• O(n²)

• O(m × n)

• O(m + n)

class Solution: def plusOne(self, digits: List[int]) -> List[int]: for i in range(len(digits) - 1, -1, -1): if digits[i] + 1 != 10: digits[i] += 1 return digits digits[i] = 0 if i == 0: return [1] + digits

• O(n)

• O(1)

• O(log n)

• O(n²)

class Solution { public: void setZeroes(vector>& matrix) { bool zeroinFirstCol = false; for (int row = 0; row < matrix.size(); row++) { if (matrix[row][0] == 0) zeroinFirstCol = true; for (int col = 1; col < matrix[0].size(); col++) { if (matrix[row][col] == 0) { matrix[row][0] = 0; matrix[0][col] = 0; } } } for (int row = matrix.size() - 1; row >= 0; row--) { for (int col = matrix[0].size() - 1; col >= 1; col--) { if (matrix[row][0] == 0 || matrix[0][col] == 0) { matrix[row][col] = 0; } } if (zeroinFirstCol) { matrix[row][0] = 0; } } } };

• O(m × n)

• O(n² log n)

• O(n)

• O(log n)

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: top = 0 bot = len(matrix) - 1 while top <= bot: mid = (top + bot) // 2 if matrix[mid][0] < target and matrix[mid][-1] > target: break elif matrix[mid][0] > target: bot = mid - 1 else: top = mid + 1 row = (top + bot) // 2 left = 0 right = len(matrix[row]) - 1 while left <= right: mid = (left + right) // 2 if matrix[row][mid] == target: return True elif matrix[row][mid] > target: right = mid - 1 else: left = mid + 1 return False

• O(n)

• O(log(m × n))

• O(m + n)

• O(n²)

class Solution: def sortColors(self, nums: List[int]) -> None: count = {} for i in range(len(nums)): count[nums[i]] = count.get(nums[i], 0) + 1 idx = 0 for color in range(3): freq = count.get(color, 0) nums[idx : idx + freq] = [color] * freq idx += freq

• O(n log n)

• O(n)

• O(n²)

• O(log n)

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] subset = [] def create_subset(i): if i == len(nums): res.append(subset[:]) return subset.append(nums[i]) create_subset(i+1) subset.pop() create_subset(i+1) create_subset(0) return res

• O(n log n)

• O(n²)

• O(2ⁿ × n)

• O(2n)

class Solution: def removeDuplicates(self, nums: List[int]) -> int: k = 2 for i in range(2, len(nums)): if nums[i] != nums[k - 2]: nums[k] = nums[i] k += 1 return k

• O(n log n)

• O(n)

• O(n²)

• O(1)