环形数组技巧

In a Nutshell

The circular array technique uses modulus (remainder) operations to transform a regular array into a logical circular array. This allows us to add or remove elements from the array's head in O(1) time.

Principle of Circular Arrays

Can an array be circular? No, an array is a block of linear, contiguous memory space, so it can't inherently have a circular concept.

However, we can make an array logically circular, as demonstrated by the following code:

java 🟢

// array of length 5
int[] arr = new int[]{1, 2, 3, 4, 5};
int i = 0;
// simulate a circular array, this loop will never end
while (i < arr.length) {
    System.out.println(arr[i]);
    i = (i + 1) % arr.length;
}

cpp 🤖

#include <iostream>
#include <vector>
using namespace std;

// array with length 5
vector<int> arr = {1, 2, 3, 4, 5};
int i = 0;
// simulate a circular array, this loop will never end
while (i < arr.size()) {
    cout << arr[i] << endl;
    i = (i + 1) % arr.size();
}

python 🤖

# array of length 5
arr = [1, 2, 3, 4, 5]
i = 0
# simulate a circular array, this loop will never end
while i < len(arr):
    print(arr[i])
    i = (i + 1) % len(arr)

go 🤖

import "fmt"

func main() {
    // array of length 5
    arr := []int{1, 2, 3, 4, 5}
    i := 0
    // simulate a circular array, this loop will never end
    for i < len(arr) {
        fmt.Println(arr[i])
        i = (i + 1) % len(arr)
    }
}

javascript 🤖

// an array of length 5
var arr = [1, 2, 3, 4, 5];
var i = 0;
// simulate a circular array, this loop will never end
while (i < arr.length) {
    console.log(arr[i]);
    i = (i + 1) % arr.length;
}

The key to this code is the modulo operation %, which calculates the remainder. When i reaches the last element of the array, (i + 1) % arr.length becomes 0, bringing it back to the beginning of the array. This creates a logical circular array that can be traversed indefinitely.

This is the circular array technique. How does this technique help us add or remove elements at the head of the array in O(1) time?

Let's say we have an array of length 6, currently holding only 3 elements, as shown below (positions without elements are marked with _):

[1, 2, 3, _, _, _]

Now we need to remove the element 1 from the head of the array. We can transform the array like this:

[_, 2, 3, _, _, _]

That is, we only mark the position of element 1 as empty without moving any data.

At this point, if we want to add elements 4 and 5 to the head of the array, we can transform the array like this:

[4, 2, 3, _, _, 5]

You can see that when there's no space at the head to add a new element, it wraps around and adds the new element to the tail.

Core Principle

The above example is just to give you an intuitive understanding of a circular array. The key to a circular array is that it maintains two pointers, start and end. The start pointer points to the index of the first valid element, and the end pointer points to the next position index after the last valid element.

Thus, when we add or remove elements at the head of the array, we only need to move the start pointer. When we add or remove elements at the tail of the array, we only need to move the end pointer.

When start or end move beyond the array boundaries (< 0 or >= arr.length), we can use the modulo operation % to make them wrap around to the head or tail of the array, thus achieving the circular array effect.

Hands-on Section

Theories are always shallow; to fully understand, you must practice.

I have implemented a simple circular array in a visualization panel. You can click arr.addLast or arr.addFirst in the code below and observe the changes in the start and end pointers as well as the elements in the arr array:

Code Implementation

Key Points, Open-Closed Interval

In my code, the interval of the circular array is defined as left-closed and right-open, that is, the interval [start, end) contains the array elements. All other methods are implemented based on the left-closed and right-open interval.

Some readers may ask, why use a left-closed and right-open interval? Can’t we use intervals that are open at both ends or closed at both ends?

When defining the boundaries of the sliding window in Sliding Window Algorithm Core Framework, similar questions arise. Let me explain here as well.

Theoretically, you can design the interval's open-closed status randomly, but generally, a left-closed and right-open interval is the most convenient to handle.

This is because, when initializing start = end = 0, the interval [0, 0) contains no elements, but as long as you move end one position to the right (expanding), the interval [0, 1) contains one element 0.

If you set the interval to be open at both ends, then moving end one position to the right results in the open interval (0, 1), which still contains no elements. If you set it to be closed at both ends, then the initial interval [0, 0] already contains one element. Both situations introduce unnecessary complications for boundary handling. If you insist on using them, you’ll need to add special handling in your code.

Finally, here is a generic Java implementation for reference:

java 🟢

public class CycleArray<T> {
    private T[] arr;
    private int start;
    private int end;
    private int count;
    private int size;

    public CycleArray() {
        this(1);
    }

    @SuppressWarnings("unchecked")
    public CycleArray(int size) {
        this.size = size;
        // Since Java does not support direct creation of generic arrays, type casting is used here
        this.arr = (T[]) new Object[size];
        // start points to the index of the first valid element, closed interval
        this.start = 0;
        // remember that end is an open interval,
        // that is, end points to the next position index of the last valid element
        this.end = 0;
        this.count = 0;
    }

    // Helper function for automatic resizing
    @SuppressWarnings("unchecked")
    private void resize(int newSize) {
        // Create a new array
        T[] newArr = (T[]) new Object[newSize];
        // Copy elements from the old array to the new array
        for (int i = 0; i < count; i++) {
            newArr[i] = arr[(start + i) % size];
        }
        arr = newArr;
        // Reset start and end pointers
        start = 0;
        end = count;
        size = newSize;
    }

    // Add element to the start of the array, time complexity O(1)
    public void addFirst(T val) {
        // When the array is full, expand to twice its original size
        if (isFull()) {
            resize(size * 2);
        }
        // Since start is a closed interval, move left first, then assign value
        start = (start - 1 + size) % size;
        arr[start] = val;
        count++;
    }

    // Remove element from the start of the array, time complexity O(1)
    public void removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // Since start is a closed interval, assign value first, then move right
        arr[start] = null;
        start = (start + 1) % size;
        count--;
        // If the number of elements in the array is reduced to one-fourth of the original size, reduce the array size by half
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // Add element to the end of the array, time complexity O(1)
    public void addLast(T val) {
        if (isFull()) {
            resize(size * 2);
        }
        // Since end is an open interval, assign value first, then move right
        arr[end] = val;
        end = (end + 1) % size;
        count++;
    }

    // Remove element from the end of the array, time complexity O(1)
    public void removeLast() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // Since end is an open interval, move left first, then assign value
        end = (end - 1 + size) % size;
        arr[end] = null;
        count--;
        // Shrink
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // Get the first element of the array, time complexity O(1)
    public T getFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        return arr[start];
    }

    // Get the last element of the array, time complexity O(1)
    public T getLast() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // end is an open interval, pointing to the next element's position, so subtract 1
        return arr[(end - 1 + size) % size];
    }

    public boolean isFull() {
        return count == size;
    }
    
    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }
}

cpp 🤖

#include <stdexcept>
#include <memory>

template <typename T>
class CycleArray {
    private:
        std::unique_ptr<T[]> arr;
        int start;
        int end;
        int count;
        int size;

        // helper function for automatic resizing
        void resize(int newSize) {
            // create a new array
            std::unique_ptr<T[]> newArr = std::make_unique<T[]>(newSize);
            // copy elements from the old array to the new array
            for (int i = 0; i < count; ++i) {
                newArr[i] = arr[(start + i) % size];
            }
            arr = std::move(newArr);
            // reset the start and end pointers
            start = 0;
            end = count;
            size = newSize;
        }

    public:
        CycleArray() : CycleArray(1) {}

        CycleArray(int size) : start(0), end(0), count(0), size(size) {
            arr = std::make_unique<T[]>(size);
        }

        // add an element to the front of the array, time complexity O(1)
        void addFirst(const T& val) {
            // if the array is full, double its size
            if (isFull()) {
                resize(size * 2);
            }
            // since start is a closed interval, move left first, then assign
            start = (start - 1 + size) % size;
            arr[start] = val;
            count++;
        }

        // remove an element from the front of the array, time complexity O(1)
        void removeFirst() {
            if (isEmpty()) {
                throw std::runtime_error("Array is empty");
            }
            // since start is a closed interval, assign first, then move right
            arr[start] = T();
            start = (start + 1) % size;
            count--;
            // if the number of elements in the array decreases to a quarter of the original size, halve the size of the array
            if (count > 0 && count == size / 4) {
                resize(size / 2);
            }
        }

        // add an element to the end of the array, time complexity O(1)
        void addLast(const T& val) {
            if (isFull()) {
                resize(size * 2);
            }
            // since end is an open interval, assign first, then move right
            arr[end] = val;
            end = (end + 1) % size;
            count++;
        }

        // remove an element from the end of the array, time complexity O(1)
        void removeLast() {
            if (isEmpty()) {
                throw std::runtime_error("Array is empty");
            }
            // since end is an open interval, move left first, then assign
            end = (end - 1 + size) % size;
            arr[end] = T();
            count--;
            // reduce the size
            if (count > 0 && count == size / 4) {
                resize(size / 2);
            }
        }

        // get the first element of the array, time complexity O(1)
        T getFirst() const {
            if (isEmpty()) {
                throw std::runtime_error("Array is empty");
            }
            return arr[start];
        }

        // get the last element of the array, time complexity O(1)
        T getLast() const {
            if (isEmpty()) {
                throw std::runtime_error("Array is empty");
            }
            // end is an open interval, pointing to the next element's position, so subtract 1
            return arr[(end - 1 + size) % size];
        }

        bool isFull() const {
            return count == size;
        }

        int getSize() const {
            return count;
        }

        bool isEmpty() const {
            return count == 0;
        }
};

python 🤖

class CycleArray:
    def __init__(self, size=1):
        self.size = size
        # Since Python supports directly creating generic arrays, no type conversion is needed
        self.arr = [None] * size
        # start points to the index of the first valid element, inclusive interval
        self.start = 0
        # remember that end is an open interval,
        # that is, end points to the index of the position after the last valid element
        self.end = 0
        self.count = 0

    # automatic resize helper function
    def resize(self, newSize):
        # create a new array
        new_arr = [None] * newSize
        # copy the elements of the old array to the new array
        for i in range(self.count):
            new_arr[i] = self.arr[(self.start + i) % self.size]
        self.arr = new_arr
        # reset start and end pointers
        self.start = 0
        self.end = self.count
        self.size = newSize

    # add an element to the head of the array, time complexity O(1)
    def add_first(self, val):
        # when the array is full, double the size
        if self.is_full():
            self.resize(self.size * 2)
        # since start is an inclusive interval, move left first, then assign value
        self.start = (self.start - 1 + self.size) % self.size
        self.arr[self.start] = val
        self.count += 1

    # remove an element from the head of the array, time complexity O(1)
    def remove_first(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # since start is an inclusive interval, assign value first, then move right
        self.arr[self.start] = None
        self.start = (self.start + 1) % self.size
        self.count -= 1
        # if the number of elements decreases to one-fourth of the original size, halve the array size
        if self.count > 0 and self.count == self.size // 4:
            self.resize(self.size // 2)

    # add an element to the tail of the array, time complexity O(1)
    def add_last(self, val):
        if self.is_full():
            self.resize(self.size * 2)
        # since end is an open interval, assign value first, then move right
        self.arr[self.end] = val
        self.end = (self.end + 1) % self.size
        self.count += 1

    # remove an element from the tail of the array, time complexity O(1)
    def remove_last(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # since end is an open interval, move left first, then assign value
        self.end = (self.end - 1 + self.size) % self.size
        self.arr[self.end] = None
        self.count -= 1
        # shrink size
        if self.count > 0 and self.count == self.size // 4:
            self.resize(self.size // 2)

    # get the head element of the array, time complexity O(1)
    def get_first(self):
        if self.is_empty():
            raise Exception("Array is empty")
        return self.arr[self.start]

    # get the tail element of the array, time complexity O(1)
    def get_last(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # end is an open interval, pointing to the next position, so subtract 1
        return self.arr[(self.end - 1 + self.size) % self.size]

    def is_full(self):
        return self.count == self.size

    def size(self):
        return self.count

    def is_empty(self):
        return self.count == 0

go 🤖

import "errors"

// CycleArray is a cyclic array data structure
type CycleArray[T any] struct {
    arr   []T
    start int
    end   int
    count int
    size  int
}

func NewCycleArray[T any]() *CycleArray[T] {
    return NewCycleArrayWithSize[T](1)
}

func NewCycleArrayWithSize[T any](size int) *CycleArray[T] {
    return &CycleArray[T]{
        arr:   make([]T, size),
        start: 0,
        end:   0,
        count: 0,
        size:  size,
    }
}

// automatic resize helper function
func (ca *CycleArray[T]) resize(newSize int) {
    // create a new array
    newArr := make([]T, newSize)
    // copy elements from the old array to the new array
    for i := 0; i < ca.count; i++ {
        newArr[i] = ca.arr[(ca.start+i)%ca.size]
    }
    ca.arr = newArr
    // reset start and end pointers
    ca.start = 0
    ca.end = ca.count
    ca.size = newSize
}

// add an element at the head of the array, time complexity O(1)
func (ca *CycleArray[T]) AddFirst(val T) {
    // when the array is full, double its size
    if ca.isFull() {
        ca.resize(ca.size * 2)
    }
    // since start is a closed interval, move left first, then assign
    ca.start = (ca.start - 1 + ca.size) % ca.size
    ca.arr[ca.start] = val
    ca.count++
}

// remove an element from the head of the array, time complexity O(1)
func (ca *CycleArray[T]) RemoveFirst() error {
    if ca.isEmpty() {
        return errors.New("array is empty")
    }
    // since start is a closed interval, assign first, then move right
    ca.arr[ca.start] = *new(T)
    ca.start = (ca.start + 1) % ca.size
    ca.count--
    // if the number of elements in the array is reduced to one-fourth of the original size, halve the array size
    if ca.count > 0 && ca.count == ca.size/4 {
        ca.resize(ca.size / 2)
    }
    return nil
}

// add an element at the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) AddLast(val T) {
    if ca.isFull() {
        ca.resize(ca.size * 2)
    }
    // since end is an open interval, assign first, then move right
    ca.arr[ca.end] = val
    ca.end = (ca.end + 1) % ca.size
    ca.count++
}

// remove an element from the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) RemoveLast() error {
    if ca.isEmpty() {
        return errors.New("array is empty")
    }
    // since end is an open interval, move left first, then assign
    ca.end = (ca.end - 1 + ca.size) % ca.size
    ca.arr[ca.end] = *new(T)
    ca.count--
    // shrink size
    if ca.count > 0 && ca.count == ca.size/4 {
        ca.resize(ca.size / 2)
    }
    return nil
}

// get the element at the head of the array, time complexity O(1)
func (ca *CycleArray[T]) GetFirst() (T, error) {
    if ca.isEmpty() {
        return *new(T), errors.New("array is empty")
    }
    return ca.arr[ca.start], nil
}

// get the element at the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) GetLast() (T, error) {
    if ca.isEmpty() {
        return *new(T), errors.New("array is empty")
    }
    // end is an open interval, pointing to the next element's position, so subtract 1
    return ca.arr[(ca.end-1+ca.size)%ca.size], nil
}

func (ca *CycleArray[T]) isFull() bool {
    return ca.count == ca.size
}

func (ca *CycleArray[T]) Size() int {
    return ca.count
}

func (ca *CycleArray[T]) isEmpty() bool {
    return ca.count == 0
}

javascript 🤖

class CycleArray {
    constructor(size = 1) {
        this.size = size;
        // No type conversion needed since JavaScript allows array creation
        this.arr = new Array(size);
        // start points to the index of the first valid element, closed interval
        this.start = 0;
        // Note that end is an open interval,
        // which means end points to the next position index after the last valid element
        this.end = 0;
        this.count = 0;
    }

    resize(newSize) {
        // Create a new array
        var newArr = new Array(newSize);
        // Copy the elements from the old array to the new array
        for (var i = 0; i < this.count; i++) {
            newArr[i] = this.arr[(this.start + i) % this.size];
        }
        this.arr = newArr;
        // Reset the start and end pointers
        this.start = 0;
        this.end = this.count;
        this.size = newSize;
    }

    // Add an element at the head of the array, time complexity O(1)
    addFirst(val) {
        // Double the size of the array if it is full
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // Since start is a closed interval, decrement first, then assign
        this.start = (this.start - 1 + this.size) % this.size;
        this.arr[this.start] = val;
        this.count++;
    }

    // Remove an element from the head of the array, time complexity O(1)
    removeFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // Since start is a closed interval, assign first, then increment
        this.arr[this.start] = null;
        this.start = (this.start + 1) % this.size;
        this.count--;
        // Shrink the array size to half if the number of elements reduces to one-fourth of the original size
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // Add an element at the tail of the array, time complexity O(1)
    addLast(val) {
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // Since end is an open interval, assign first, then increment
        this.arr[this.end] = val;
        this.end = (this.end + 1) % this.size;
        this.count++;
    }

    // Remove an element from the tail of the array, time complexity O(1)
    removeLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // Since end is an open interval, decrement first, then assign
        this.end = (this.end - 1 + this.size) % this.size;
        this.arr[this.end] = null;
        this.count--;
        // Shrink the array size
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // Get the element at the head of the array, time complexity O(1)
    getFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        return this.arr[this.start];
    }

    // Get the element at the tail of the array, time complexity O(1)
    getLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // end is an open interval pointing to the next element's position, so subtract 1
        return this.arr[(this.end - 1 + this.size) % this.size];
    }

    isFull() {
        return this.count === this.size;
    }

    size() {
        return this.count;
    }

    isEmpty() {
        return this.count === 0;
    }
}

Thought Exercise

Is the Efficiency of Adding/Removing Elements at the Array Head Really Only `O(N)`?

We often say that the time complexity of adding or removing elements at the head of an array is O(N) because we need to shift elements. However, if we use a circular array, we can actually achieve this in O(1) time complexity.

Of course, the circular array implementation mentioned above only provides methods like addFirst, removeFirst, addLast, and removeLast. It does not offer certain methods from the dynamic array implementation we discussed earlier, such as removing elements at a specific index, accessing elements at a specific index, or inserting elements at a specific index.

But think about it, can't a circular array implement these methods? Does the time complexity of these operations degrade compared to a regular array?

It doesn't seem so.

A circular array can also remove elements at a specific index and requires data shifting, just like a regular array, with a complexity of O(N).

A circular array can also access elements at a specific index (random access). Although it doesn't directly access the corresponding index, it calculates the real index through start. The time complexity of calculation and access remains O(1).

A circular array can also insert elements at a specific index, which also requires data shifting, just like a regular array, with a complexity of O(N).

Think about whether this is true. If it is, why don't the dynamic array containers in the standard libraries of programming languages use the circular array technique?