6.4 Developing Algorithms Using Arrays

Arrays aren't just for storing data—they're powerful tools for solving many types of problems. In this guide, we'll explore common algorithms that use arrays to process data in useful ways. These standard patterns will help you solve a wide range of programming challenges on the AP exam and beyond.

Standard Array Algorithms

Let's look at some of the most common and useful algorithms that use array traversal:

Finding a Minimum or Maximum Value

This algorithm finds the smallest or largest value in an array. We'll use the data type int (integer) for our examples, but these algorithms work with other numeric types too:

public static int findMinimum(int[] arr) {
    // Start by assuming the first element is the minimum
    int min = arr[0];
    
    // Check each element to see if it's smaller
    for (int value : arr) {
        if (value < min) {
            min = value;
        }
    }
    
    return min;
}

For finding the maximum, just change < to >:

public static int findMaximum(int[] arr) {
    int max = arr[0];
    
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    
    return max;
}

Computing a Sum or Average

A common operation is calculating the sum of all values in an array, which means adding up all the elements. This can then be used to find the average:

public static double calculateAverage(int[] arr) {
    int sum = 0;
    
    // Add up all values
    for (int value : arr) {
        sum += value;
    }
    
    // Calculate and return the average
    return (double) sum / arr.length;
}

Finding the Mode (Most Frequent Value)

The mode is the value that appears most often:

public static int findMode(int[] arr) {
    int mode = arr[0];
    int maxCount = 0;
    
    for (int i = 0; i < arr.length; i++) {
        int count = 0;
        
        // Count how many times arr[i] appears
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == arr[i]) {
                count++;
            }
        }
        
        // If this count is higher, we have a new mode
        if (count > maxCount) {
            maxCount = count;
            mode = arr[i];
        }
    }
    
    return mode;
}

Checking If at Least One Element Has a Property

This pattern tests if any element meets a condition:

public static boolean hasNegativeNumber(int[] arr) {
    for (int value : arr) {
        if (value < 0) {
            return true;  // Found at least one!
        }
    }
    
    return false;  // None found
}

Checking If All Elements Have a Property

This pattern tests if every element meets a condition:

public static boolean allPositive(int[] arr) {
    for (int value : arr) {
        if (value <= 0) {
            return false;  // Found one that doesn't match
        }
    }
    
    return true;  // All elements passed the test
}

Processing Consecutive Pairs of Elements

This pattern examines adjacent elements in the array to find pairs that have a specific relationship:

public static boolean hasConsecutiveIdenticalValues(int[] arr) {
    // Need at least 2 elements to have a pair
    if (arr.length < 2) {
        return false;
    }
    
    // Check each adjacent pair
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            return true;  // Found consecutive identical values
        }
    }
    
    return false;  // No consecutive identical values found
}

Counting Elements Meeting Specific Criteria

This pattern counts elements that satisfy a condition:

public static int countEvenNumbers(int[] arr) {
    int count = 0;
    
    for (int value : arr) {
        if (value % 2 == 0) {  // Check if even
            count++;
        }
    }
    
    return count;
}

Checking for Duplicates

Duplicates are values that appear more than once in an array. This pattern detects if any value appears more than once:

public static boolean hasDuplicates(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                return true;  // Found duplicates
            }
        }
    }
    
    return false;  // No duplicates found
}

Array Manipulation Algorithms

These algorithms actually change the array structure:

Shifting Elements

This pattern moves all elements one position to the left or right. The methods shiftRight and shiftLeft demonstrate these operations:

// Shift all elements right by 1 (losing the last element)
public static void shiftRight(int[] arr) {
    // Start from the right end (except the last element)
    for (int i = arr.length - 2; i >= 0; i--) {
        arr[i + 1] = arr[i];
    }
    
    // The first position gets a default value (often 0)
    arr[0] = 0;
}

// Shift all elements left by 1 (losing the first element)
public static void shiftLeft(int[] arr) {
    // Start from the left end (except the first element)
    for (int i = 0; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    // The last position gets a default value
    arr[arr.length - 1] = 0;

}

Rotating Elements

Rotation is like shifting, but the element that falls off one end appears at the other end:

// Rotate all elements right by 1
public static void rotateRight(int[] arr) {
    if (arr.length <= 1) {
        return;  // Nothing to rotate
    }
    
    // Save the last element
    int last = arr[arr.length - 1];
    
    // Shift everything right
    for (int i = arr.length - 2; i >= 0; i--) {
        arr[i + 1] = arr[i];
    }
    
    // Put the saved element at the beginning
    arr[0] = last;
}

Reversing the Order of Elements

This pattern flips the order of the array:

public static void reverseArray(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    
    // Swap elements from outside toward the middle
    while (left < right) {
        // Swap arr[left] and arr[right]
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        
        // Move toward the center
        left++;
        right--;
    }
}

Developing Your Own Algorithms

When writing your own array algorithms, follow these steps:

1. Understand the problem: What exactly needs to be done?
2. Choose the right traversal: Will a simple for-each loop work, or do you need index access?
3. Start with simple cases: Trace your algorithm with a small example
4. Handle edge cases: What if the array is empty? Has just one element?
5. Test your solution: Try multiple inputs, including special cases

Common Algorithm Patterns

Example: Combining Multiple Techniques

Here's an algorithm that finds the two largest values in an array:

public static int[] findTwoLargest(int[] arr) {
    if (arr.length < 2) {
        // Not enough elements
        return arr;
    }
    
    // Start with the first two elements
    int largest = Math.max(arr[0], arr[1]);
    int secondLargest = Math.min(arr[0], arr[1]);
    
    // Check the rest of the array
    for (int i = 2; i < arr.length; i++) {
        if (arr[i] > largest) {
            // New largest found, current largest becomes second
            secondLargest = largest;
            largest = arr[i];
        } else if (arr[i] > secondLargest) {
            // New second largest found
            secondLargest = arr[i];
        }
    }
    
    return new int[] {largest, secondLargest};
}

Another Example: Finding a Majority Element

Here's an algorithm that finds if there's a value that appears more than half the time:

public static boolean hasMajorityElement(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int count = 0;
        
        // Count how many times arr[i] appears
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == arr[i]) {
                count++;
            }
        }
        
        // Check if it's a majority element
        if (count > arr.length / 2) {
            return true;
        }
    }
    
    return false;
}

Summary

Array algorithms are powerful tools for processing collections of data. We've covered standard algorithms for finding minimums, maximums, sums, averages, modes, and checking for various properties. We've also explored algorithms that manipulate arrays by shifting, rotating, and reversing elements. Being familiar with these patterns will help you solve a wide range of programming problems by recognizing which standard algorithm to apply or how to modify one to fit your needs.