Second Largest

What You'll Learn

Finding specific elements in a single pass.

Real-World Context

"Like finding the runner-up in a race without sorting the entire list of participants."

Breaking It Down

Initialize largest and second_largest to negative infinity
Iterate through the array
If current > largest, update second_largest to largest, then largest to current
Else if current > second_largest and current != largest, update second_largest

Python 3

def second_largest(arr):
    largest = second = float('-inf')
    for x in arr:
        if x > largest:
            second = largest
            largest = x
        elif x > second and x != largest:
            second = x
    return second

Line-by-Line Walkthrough

The key is to update the 'runner-up' whenever we find a new 'winner'. This allows us to find the answer in one pass (O(N)) instead of sorting (O(N log N)).

Complexity Analysis

Time: O(N)
Space: O(1)
We only visit each element once and use two variables.

Common Mistakes

❌ Sorting the array first
✅ Sorting takes O(N log N). A single pass is O(N) and much more efficient.

Try It Yourself

How would you find the K-th largest element?

Missing Number

What You'll Learn

Using mathematical formulas for array problems.

Real-World Context

"You have numbers from 1 to 100, but one is missing. How do you find it without checking every single one?"

Breaking It Down

Calculate the expected sum of 1 to N using formula: N*(N+1)/2
Calculate the actual sum of elements in the array
Missing number = Expected Sum - Actual Sum

Python 3

def find_missing(arr, n):
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

Line-by-Line Walkthrough

This is a beautiful example of using math to solve a coding problem. The sum of first N natural numbers is a constant time calculation.

Complexity Analysis

Time: O(N)
Space: O(1)
We sum the array once.

Common Mistakes

❌ Potential integer overflow for very large N
✅ Use long long in C++ or the XOR approach to avoid large sums.

Try It Yourself

Can you solve this using the XOR operator? (Hint: XOR all numbers from 1 to N and all numbers in the array)

Rotate Array

What You'll Learn

Array manipulation and the 'reversal trick'.

Real-World Context

"Shifting elements to the right by K positions. [1,2,3,4,5] rotated by 2 becomes [4,5,1,2,3]."

Breaking It Down

Reverse the entire array
Reverse the first K elements
Reverse the remaining N-K elements

Python 3

def rotate(arr, k):
    n = len(arr)
    k %= n
    arr.reverse()
    arr[:k] = reversed(arr[:k])
    arr[k:] = reversed(arr[k:])
    return arr

Line-by-Line Walkthrough

The reversal trick is the most elegant way to rotate an array in-place. It avoids using extra space for a temporary array.

Complexity Analysis

Time: O(N)
Space: O(1)
We perform three reversals, each visiting elements once.

Common Mistakes

❌ Not handling k > n
✅ Always use k = k % n to handle cases where rotation count is larger than array size.

Try It Yourself

Can you rotate the array to the left instead of the right?

Searching & Sorting

The bread and butter of algorithm interviews.

Binary Search

What You'll Learn

The 'Divide and Conquer' strategy.

Real-World Context

"Finding a name in a sorted phone book by opening it in the middle, then narrowing down the half."

Breaking It Down

Set low = 0, high = n-1
While low <= high, find mid = (low + high) / 2
If arr[mid] == target, return mid
If arr[mid] < target, low = mid + 1
Else high = mid - 1

Python 3

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Line-by-Line Walkthrough

Binary search is incredibly fast (O(log N)). For an array of 1 million elements, it only takes about 20 steps to find any number!

Complexity Analysis

Time: O(log N)
Space: O(1)
We halve the search space in each step.

Common Mistakes

❌ Using (low + high) / 2
✅ In some languages, this can cause overflow. Use low + (high - low) / 2 instead.

Try It Yourself

What happens if the array is not sorted? Can you still use binary search?

Bubble Sort

What You'll Learn

The simplest (but slowest) sorting algorithm.

Real-World Context

"Like bubbles rising in a glass of soda - the largest elements 'bubble up' to the end of the array."

Breaking It Down

Compare adjacent elements
Swap them if they are in the wrong order
Repeat for all elements until sorted

Python 3

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break
    return arr

Line-by-Line Walkthrough

Bubble sort is great for learning but inefficient for large data. The 'swapped' flag is an optimization to stop early if the array is already sorted.

Complexity Analysis

Time: O(N²)
Space: O(1)
Nested loops to compare every pair.

Common Mistakes

❌ Not using the 'swapped' optimization
✅ Without it, the algorithm always runs O(N²) even if the array is already sorted.

Try It Yourself

Can you implement Selection Sort? How is it different from Bubble Sort?

Reverse Array

What You'll Learn

In-place swapping with two pointers.

Real-World Context

"Flipping the order of elements. [1, 2, 3] becomes [3, 2, 1]."

Breaking It Down

Initialize left = 0, right = n-1
While left < right, swap arr[left] and arr[right]
Increment left, decrement right

Python 3

def reverse_array(arr):
    return arr[::-1]

# In-place
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Line-by-Line Walkthrough

The two-pointer approach is the most efficient way to reverse an array in-place without using extra memory.

Complexity Analysis

Time: O(N)
Space: O(1)
We visit each element once and swap in-place.

Common Mistakes

❌ Iterating through the whole array
✅ If you swap everything, you'll swap them twice and end up with the original array! Stop at the middle.

Try It Yourself

Can you reverse an array using recursion?

Max and Min

What You'll Learn

Linear scan to find extremes.

Real-World Context

"Finding the highest and lowest values in a list."

Breaking It Down

Initialize max and min with the first element
Iterate through the rest of the array
Update max if current > max
Update min if current < min

Python 3

def find_max_min(arr):
    if not arr: return None, None
    max_val = min_val = arr[0]
    for x in arr:
        if x > max_val: max_val = x
        if x < min_val: min_val = x
    return max_val, min_val

Line-by-Line Walkthrough

A single pass through the array is enough to find both the maximum and minimum values.

Complexity Analysis

Time: O(N)
Space: O(1)
We visit each element once.

Common Mistakes

❌ Initializing max/min with 0
✅ If all numbers are negative, max will incorrectly stay 0. Always initialize with the first element or infinity.

Try It Yourself

Can you find the max and min using the minimum number of comparisons? (Hint: Compare in pairs)

Check Sorted

What You'll Learn

Validating order in a single pass.

Real-World Context

"Checking if a list is already in ascending order."

Breaking It Down

Iterate from index 1 to n-1
If arr[i] < arr[i-1], return False
If loop finishes, return True

Python 3

def is_sorted(arr):
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            return False
    return True

Line-by-Line Walkthrough

We only need to check if every element is greater than or equal to the one before it.

Complexity Analysis

Time: O(N)
Space: O(1)
We visit each element once.

Common Mistakes

❌ Checking all pairs (O(N²))
✅ You only need to check adjacent pairs to verify if the whole array is sorted.

Try It Yourself

How would you check if an array is sorted in descending order?

Find Duplicates

What You'll Learn

Using sets or frequency maps for existence checks.

Real-World Context

"Finding all numbers that appear more than once in a list."

Breaking It Down

Create an empty set for seen elements
Create an empty set for duplicates
Iterate through the array
If element in seen, add to duplicates
Else add to seen

Python 3

def find_duplicates(arr):
    seen = set()
    dups = set()
    for x in arr:
        if x in seen:
            dups.add(x)
        else:
            seen.add(x)
    return list(dups)

Line-by-Line Walkthrough

Using a Hash Set (unordered_set) allows us to check for existence in O(1) time on average.

Complexity Analysis

Time: O(N)
Space: O(N)
We store elements in a set.

Common Mistakes

❌ Using nested loops (O(N²))
✅ Hashing is much faster for large arrays.

Try It Yourself

Can you find duplicates in O(N) time and O(1) space if the numbers are in the range [0, n-1]?

Selection Sort

What You'll Learn

Finding the minimum and placing it at the start.

Real-World Context

"Sorting by repeatedly picking the smallest remaining element."

Breaking It Down

Find the minimum element in the unsorted part
Swap it with the first element of the unsorted part
Repeat for the rest of the array

Python 3

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Line-by-Line Walkthrough

Selection sort performs fewer swaps than bubble sort but still has O(N²) time complexity.

Complexity Analysis

Time: O(N²)
Space: O(1)
Nested loops to find the minimum.

Common Mistakes

❌ Thinking it's faster than Bubble Sort
✅ Both are O(N²), but Selection Sort is generally better because it does fewer swaps.

Try It Yourself

Is Selection Sort stable? (Does it preserve the relative order of equal elements?)

Insertion Sort

What You'll Learn

Building a sorted array one element at a time.

Real-World Context

"Like sorting a hand of playing cards. You take one card and insert it into its correct position among the cards you're already holding."

Breaking It Down

Start from the second element
Compare it with elements to its left
Shift elements to the right until you find the correct spot
Insert the element

Python 3

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Line-by-Line Walkthrough

Insertion sort is very efficient for small datasets or arrays that are already mostly sorted.

Complexity Analysis

Time: O(N²)
Space: O(1)
Nested loops to shift elements.

Common Mistakes

❌ Using it for large datasets
✅ For large data, use Merge Sort or Quick Sort (O(N log N)).

Try It Yourself

Can you implement Insertion Sort using recursion?

Linear Search

What You'll Learn

The most basic searching algorithm.

Real-World Context

"Checking every element one by one until you find the target."

Breaking It Down

Iterate through the array
If current element == target, return index
If loop finishes, return -1

Python 3

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Line-by-Line Walkthrough

Linear search is the only option if the array is not sorted.

Complexity Analysis

Time: O(N)
Space: O(1)
In the worst case, we check every element.

Common Mistakes

❌ Using linear search on a sorted array
✅ Use Binary Search (O(log N)) if the array is sorted.

Try It Yourself

How would you find all occurrences of a target instead of just the first one?

Array Mastery Continued

You've covered the core array patterns. The remaining questions like "Intersection", "Union", and "Pairs with Sum" often use Hashing or Two-Pointer techniques.

Next: Recursion & Linked Lists →