Array Traversal Pattern — Problem: Find Maximum Element in an Array

Problem

Given an array of integers, find the largest element in it. You need to scan through all elements and return the one with the highest value.

Example

Input: [3, 7, 2, 9, 5]
Output: 9

Pattern: Array Traversal (Linear Scan)

A common pattern where we visit each element of an array one by one (sequentially or recursively) to perform an operation — such as finding a maximum, minimum, sum, or count.

Core idea

Move through every element in the array **exactly once**, keeping track of the needed result (like the current maximum).

Realtime analogy

Looking for the Tallest Person in a Queue

Step-by-step flow

Start
  |
  v
Initialize max = 1 (first element)
  |
  v
Compare next element → 3
  |
  +-- Is 3 > max (1)? --> Yes --> Update max = 3
  |                              
  |--> No  --> max remains 1
  |
  v
Compare next element → 5
  |
  +-- Is 5 > max (3)? --> Yes --> Update max = 5
  |
  v
Compare next element → 2
  |
  +-- Is 2 > max (5)? --> No --> max remains 5
  |
  v
Compare next element → 4
  |
  +-- Is 4 > max (5)? --> No --> max remains 5
  |
  v
End: max = 5

Solution

fun findMaxElement(numbers: IntArray): Int? {
    if (numbers.isEmpty()) return null
    var max = numbers.first()
    numbers.forEach { num ->
        if (num > max)
            max = num
    }
    return max
}

Time Complexity

Space Complexity

We only need:

We **could solve this max-finding problem using Divide and Conquer** by splitting the array, finding the max in each half, and then combining the results. However, for **small arrays**, this is **overkill** — a simple linear scan is faster and simpler.

Divide and Conquer (D&C) Pattern:

Realtime analogy

Finding the Tallest Person in a Huge Crowd

Step-bystep flow

Start
  |
  v
Check array size
  |
  +-- Is array size 1? --> Yes --> Return that element as max
  |                          |
  |                          v
  |                     End recursion
  |
  --> No --> Split array into two halves
  |             |
  |             v
  |       Recur on left half --> LeftMax
  |       Recur on right half --> RightMax
  |
  v
Compare LeftMax and RightMax
  |
  +-- Which is greater? --> That is the max of current array
  |
  v
Return max to previous recursion / combine step
  |
  v
End: max of original array

solution

fun dcFindMaxElement(numbers: IntArray, start: Int = 0, end: Int = numbers.size - 1): Int {
    if (start == end) return numbers[start]
    val mid = (start + end) / 2 // bracket is important
    val leftMax = dcFindMaxElement(numbers,start,mid)
    val rightMax = dcFindMaxElement(numbers,mid+1,end)
    return maxOf(leftMax,rightMax)
}

Time Complexity

Space Complexity

D&C visits all elements → O(n) time, recursion stack → O(log n) space.

Conclusion: Linear Scan vs Divide & Conquer

Linear Scan:

Divide & Conquer:

Takeaway