Basic DSA Patterns: Building Blocks for Problem Solving

Many algorithm problems look different on the surface, but their solutions are often built from the same small set of techniques. Once you understand these patterns, you can recognize them in unfamiliar problems and combine them to solve more complex ones.

This guide starts with small building blocks and will grow as we add new patterns. It begins with swapping values safely and finding a value efficiently in a sorted array, then extends binary search to locate the full range occupied by duplicate values.

Pattern 1: Swap two values without losing data

Suppose we want to swap the first two values in an array:

before: [7, 12, 4]
after:  [12, 7, 4]

If we immediately copy 12 over 7, the original 7 is lost. A temporary variable preserves it while we update the two positions:

1. Copy the first value into temporary.
2. Copy the second value into the first position.
3. Copy temporary into the second position.

public static class ArrayPatterns
{
    public static void Swap(int[] values, int firstIndex, int secondIndex)
    {
        int temporary = values[firstIndex];
        values[firstIndex] = values[secondIndex];
        values[secondIndex] = temporary;
    }
}

def swap(values: list[int], first_index: int, second_index: int) -> None:
    temporary = values[first_index]
    values[first_index] = values[second_index]
    values[second_index] = temporary

func Swap(values []int, firstIndex, secondIndex int) {
	temporary := values[firstIndex]
	values[firstIndex] = values[secondIndex]
	values[secondIndex] = temporary
}

Each version changes the original array, list, or slice in place. The examples assume both indexes are valid; swapping an index with itself is also safe.

Why it works

The temporary variable keeps the original first value alive after its position is overwritten. Once the second value has moved into that position, we can safely copy the saved value into the second position.

Complexity

• Time: O(1) because the swap always uses three assignments.
• Extra space: O(1) because it stores only one temporary value.

This small operation appears in array reversal, two-pointer algorithms, quick-sort partitioning, and heap operations.

Pattern 2: Find a value with binary search

Binary search finds a target in an ascending sorted array by repeatedly discarding half of the remaining search range. The sorted order is essential: without it, comparing the middle value cannot tell us which half is safe to discard.

For example:

values: [3, 7, 12, 18, 25]
target: 18

range [0, 4] -> middle 2 -> 12 is too small, so move left to 3
range [3, 4] -> middle 3 -> 18 is the target

The algorithm keeps an inclusive range from left to right:

1. Start with left at the first index and right at the last.
2. While left <= right, inspect the middle value.
3. Return the middle index when it equals the target.
4. If it is smaller than the target, continue to the right of the middle; otherwise, continue to the left.
5. Return -1 when the range becomes empty.

public static class SearchPatterns
{
    public static int BinarySearch(int[] values, int target)
    {
        int left = 0;
        int right = values.Length - 1;

        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            int candidate = values[middle];

            if (candidate == target)
                return middle;

            if (candidate < target)
                left = middle + 1;
            else
                right = middle - 1;
        }

        return -1;
    }
}

def binary_search(values: list[int], target: int) -> int:
    left = 0
    right = len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2
        candidate = values[middle]

        if candidate == target:
            return middle

        if candidate < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

func BinarySearch(values []int, target int) int {
	left := 0
	right := len(values) - 1

	for left <= right {
		middle := left + (right-left)/2
		candidate := values[middle]

		if candidate == target {
			return middle
		}

		if candidate < target {
			left = middle + 1
		} else {
			right = middle - 1
		}
	}

	return -1
}

Each version returns the index of a matching value or -1 when no match exists. An empty array therefore returns -1 without entering the loop.

Why it works

Throughout the loop, if the target exists, it must remain inside [left, right]. Because the array is sorted, a middle value smaller than the target also rules out every value to its left. A larger middle value rules out every value to its right.

Complexity

• Time: O(log n) because every comparison removes approximately half of the remaining range.
• Extra space: O(1) because the iterative version stores only a few indexes and the middle value.

With duplicate values, this basic version may return any matching index. Variations of the same pattern can find the first match, last match, or insertion position. If the input is not already sorted, sorting it first costs O(n log n), so a linear scan may be better for a single search.

Pattern 2.1: Find the first and last position of a target

A normal binary search can stop as soon as it finds the target. That is not enough when the sorted array contains duplicates and we need the complete range occupied by that value, as in Find First and Last Position of Element in Sorted Array.

For example:

values: [5, 7, 7, 8, 8, 10]
target: 8
result: [3, 4]

Finding one match and then scanning outward would work, but it can fall back to O(n) when many values equal the target. To preserve binary search’s logarithmic runtime, we search for each boundary separately.

The important change is what happens after finding a match. We save its index, but continue searching:

• To find the first position, move right to middle - 1 and look farther left.
• To find the last position, move left to middle + 1 and look farther right.

We run the boundary search twice. If the first search returns -1, the target is absent and we can immediately return [-1, -1].

public static class SearchPatterns
{
    public static int[] FindFirstAndLastPosition(int[] values, int target)
    {
        int first = FindBoundary(values, target, findFirst: true);

        if (first == -1)
            return new[] { -1, -1 };

        int last = FindBoundary(values, target, findFirst: false);
        return new[] { first, last };
    }

    private static int FindBoundary(
        int[] values,
        int target,
        bool findFirst)
    {
        int left = 0;
        int right = values.Length - 1;
        int boundary = -1;

        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            int candidate = values[middle];

            if (candidate < target)
            {
                left = middle + 1;
            }
            else if (candidate > target)
            {
                right = middle - 1;
            }
            else
            {
                boundary = middle;

                if (findFirst)
                    right = middle - 1;
                else
                    left = middle + 1;
            }
        }

        return boundary;
    }
}

def find_first_and_last_position(
    values: list[int], target: int
) -> list[int]:
    def find_boundary(find_first: bool) -> int:
        left = 0
        right = len(values) - 1
        boundary = -1

        while left <= right:
            middle = left + (right - left) // 2
            candidate = values[middle]

            if candidate < target:
                left = middle + 1
            elif candidate > target:
                right = middle - 1
            else:
                boundary = middle

                if find_first:
                    right = middle - 1
                else:
                    left = middle + 1

        return boundary

    first = find_boundary(find_first=True)

    if first == -1:
        return [-1, -1]

    last = find_boundary(find_first=False)
    return [first, last]

func FindFirstAndLastPosition(values []int, target int) []int {
	findBoundary := func(findFirst bool) int {
		left := 0
		right := len(values) - 1
		boundary := -1

		for left <= right {
			middle := left + (right-left)/2
			candidate := values[middle]

			if candidate < target {
				left = middle + 1
			} else if candidate > target {
				right = middle - 1
			} else {
				boundary = middle

				if findFirst {
					right = middle - 1
				} else {
					left = middle + 1
				}
			}
		}

		return boundary
	}

	first := findBoundary(true)

	if first == -1 {
		return []int{-1, -1}
	}

	last := findBoundary(false)
	return []int{first, last}
}

Why it works

Each search remembers the best boundary found so far. Moving left after a match cannot hide an earlier occurrence, and moving right cannot hide a later one. Sorted order still lets us discard the opposite half whenever the middle value is smaller or larger than the target.

Returning immediately on equality would lose this behaviour: it would give us a valid match, but not necessarily the first or last one.

Complexity

• Time: O(log n). Two binary searches are still O(log n) because constant factors do not change Big O.
• Extra space: O(1) because the searches keep only indexes and a saved boundary.

The same code handles an empty array, a missing target, a single occurrence, and an array containing only duplicates.