1. Find the maximum element in an array
Given an array, find the maximum element without using the built-in max() function.
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
print(find_max([3, 7, 1, 9, 5]))
Example Output: 9
We keep track of the maximum element seen so far.
Each new element is compared with the current maximum.
Time Complexity: O(n), Space: O(1).
2. Reverse an array
Reverse the given array in-place without using extra space.
def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
print(reverse_array([1,2,3,4,5]))
Example Output: [5, 4, 3, 2, 1]
Swap the first element with the last, second with second-last, and so on.
Time Complexity: O(n), Space: O(1).
3. Find the missing number
Array contains numbers from 1 to N with one number missing. Find the missing number.
def missing_number(arr, n):
expected_sum = n * (n + 1) // 2
return expected_sum - sum(arr)
print(missing_number([1,2,4,5,6], 6))
Example Output: 3
Sum of 1..N is known. Subtract the actual sum of array.
The difference is the missing number.
Time Complexity: O(n), Space: O(1).
4. Move zeros to the end
Move all zeros to the end of the array while maintaining relative order.
def move_zeros(arr):
pos = 0
for num in arr:
if num != 0:
arr[pos] = num
pos += 1
while pos < len(arr):
arr[pos] = 0
pos += 1
return arr
print(move_zeros([0,1,0,3,12]))
Example Output: [1, 3, 12, 0, 0]
Non-zero elements are placed first, then remaining slots filled with 0.
Time Complexity: O(n), Space: O(1).
5. Find the first repeating element
Return the first element that appears more than once in the array.
def first_repeating(arr):
seen = set()
for num in arr:
if num in seen:
return num
seen.add(num)
return None
print(first_repeating([2,5,1,2,3,5]))
Example Output: 2
Use a set to remember elements we’ve already seen.
If we encounter the same element again, return it.
Time Complexity: O(n), Space: O(n).
6. Maximum subarray sum (Kadane’s Algorithm)
Find the contiguous subarray with the maximum sum.
def max_subarray_sum(arr):
max_ending = max_so_far = arr[0]
for num in arr[1:]:
max_ending = max(num, max_ending + num)
max_so_far = max(max_so_far, max_ending)
return max_so_far
print(max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]))
Example Output: 6 (subarray: [4, -1, 2, 1])
We track the best subarray ending at each index.
At each step: either extend previous subarray or start fresh.
Time Complexity: O(n), Space: O(1).
7. Find leaders in the array
An element is a leader if it is greater than all elements to its right.
def leaders(arr):
n = len(arr)
max_from_right = arr[-1]
result = [max_from_right]
for i in range(n-2, -1, -1):
if arr[i] > max_from_right:
result.append(arr[i])
max_from_right = arr[i]
return result[::-1]
print(leaders([16,17,4,3,5,2]))
Example Output: [17, 5, 2]
Start from rightmost element (always a leader).
Keep track of max seen so far from right, add leaders.
Time Complexity: O(n), Space: O(1).
8. Find the equilibrium index
Index where sum of left part equals sum of right part.
def equilibrium_index(arr):
total = sum(arr)
left_sum = 0
for i, num in enumerate(arr):
total -= num
if left_sum == total:
return i
left_sum += num
return -1
print(equilibrium_index([1,3,5,2,2]))
Example Output: 2 (index 2 → value 5)
Maintain running left sum. Right sum = total - left_sum - current.
Check equality at each index.
Time Complexity: O(n), Space: O(1).
9. Longest consecutive subsequence (Difficult)
Given an unsorted array, find the length of the longest consecutive elements sequence.
def longest_consecutive(arr):
num_set = set(arr)
longest = 0
for num in num_set:
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
longest = max(longest, length)
return longest
print(longest_consecutive([100,4,200,1,3,2]))
Example Output: 4 (sequence: [1, 2, 3, 4])
Use a set for O(1) lookups. Only start counting from sequence “beginnings” (num-1 not in set).
Time Complexity: O(n), Space: O(n).
10. Trapping Rain Water (Difficult)
Given heights of bars, calculate total trapped rainwater.
def trap_rain_water(height):
n = len(height)
if n == 0: return 0
left, right = [0]*n, [0]*n
left[0] = height[0]
for i in range(1, n):
left[i] = max(left[i-1], height[i])
right[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right[i] = max(right[i+1], height[i])
trapped = 0
for i in range(n):
trapped += min(left[i], right[i]) - height[i]
return trapped
print(trap_rain_water([0,1,0,2,1,0,1,3,2,1,2,1]))
Example Output: 6
For each bar, water trapped = min(max_left, max_right) - height[i].
Precompute left & right max arrays.
Time Complexity: O(n), Space: O(n).
11. Maximum product subarray (Difficult)
Find the contiguous subarray with maximum product.
def max_product_subarray(arr):
max_prod = min_prod = result = arr[0]
for num in arr[1:]:
if num < 0:
max_prod, min_prod = min_prod, max_prod
max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)
result = max(result, max_prod)
return result
print(max_product_subarray([2,3,-2,4]))
Example Output: 6 (subarray: [2, 3])
Keep track of both max and min products at each step (because negative * negative = positive).
Swap when negative appears.
Time Complexity: O(n), Space: O(1).