Subarray

A subarray is a contiguous portion of an array taken from a starting index i to an ending index j, where 0 <= i <= j and the elements included are a[i], a[i+1], ..., a[j]. The length of this subarray is j - i + 1. Subarrays are defined with respect to the original array and preserve the order of elements.

For example, in the array [5, 7, -2, 3, 9], the subarray from index 1 to 3 is [7, -2, 3]. The entire array [5, 7, -2, 3, 9] is also a subarray, as is any single-element array like [ -2 ]. The notion of an empty subarray exists in some contexts but is not universally used.

Difference from subsequence: A subarray must be contiguous, meaning no elements are skipped between the endpoints. A subsequence allows gaps, so elements can be selected in order without requiring contiguity.

Applications and properties: Subarrays are central to many algorithmic problems, such as finding the maximum subarray sum (Kadane’s algorithm), counting subarrays with a given sum or product, or determining the minimum-length subarray that satisfies certain conditions. The total number of subarrays of an array of length n is n(n + 1)/2.

Computation: Subarray sums can be computed efficiently with prefix sums, enabling O(1) queries for any i..j after O(n) preprocessing. In two dimensions, the analogous concept refers to a submatrix, defined by contiguous ranges of rows and columns.

Terminology: In strings, a similar concept is called a substring; the idea is parallel to a 1D subarray in most contexts.