Array Basics | Developer Knowledge Base

Arrays are the most important entry point into algorithmic thinking: fixed-size, contiguous, index-driven, and the base layer under many LeetCode patterns.

1. Definition

What is an array?

An array is a fixed-size sequence of elements stored next to each other in memory. That layout is the reason index access is fast, scans are predictable, and middle insertions are expensive.

Why does it exist?

Arrays exist because many problems need compact storage and direct access by position. If the computer can calculate where the $i$-th element lives, it can jump there immediately instead of walking through previous elements.

Where does it fit?

Arrays are usually the first data structure to consider when:

the input is already a list of values,
order matters,
indices matter,
in-place modification is allowed,
or a later pattern like two pointers, sliding window, prefix sum, binary search, or DP will build on top of the input.

Intuition

Think of an array like numbered lockers in one hallway. If someone asks for locker 17, you do not check lockers 0 to 16 first. You go straight to locker 17 because the position is computable. That is why array indexing is typically O(1).

Java context

In Java, arrays are objects. They live on the heap, have a fixed length, know their runtime component type, and perform bounds checks on access. That means arrays are lower-level than most collections, but still safer than raw memory manipulation.

2. Core Concepts

2.1 Contiguous memory

The core array idea is contiguous storage. Conceptually, if the first element starts at some base position and each element size is known, then the address of index i is:

$$ \text{address}(i) = \text{base} + i \cdot \text{elementSize} $$

You do not write address arithmetic in Java, but this model explains the performance profile.

2.2 Fixed size

Array size does not change after creation.

int[] scores = new int[5];
System.out.println(scores.length); // 5

If you need more capacity, you allocate a new array and copy the values. That is the main reason dynamic arrays such as ArrayList exist.

2.3 Zero-based indexing

Arrays use zero-based indexing:

first element → 0
second element → 1
last element → length - 1

This is simple, but many interview bugs are still off-by-one mistakes.

2.4 Time complexity

Operation	Complexity	Why
Read by index	`O(1)`	Direct jump by index
Write by index	`O(1)`	Direct overwrite
Full scan	`O(n)`	Must inspect elements
Search in unsorted array	`O(n)`	May inspect all elements
Insert in middle	`O(n)`	Later elements shift
Delete in middle	`O(n)`	Later elements shift

2.5 Space complexity

If the input array already exists and you only use a few helper variables, extra space is O(1). If you allocate another array of size n, extra space is O(n). Interviewers care about this because two solutions with similar time cost may differ a lot in memory behavior.

2.6 In-place updates

In-place means you modify the original array rather than allocating another full structure.

import java.util.Arrays;

int[] nums = {1, 2, 3};
nums[1] = 99;
System.out.println(Arrays.toString(nums)); // [1, 99, 3]

This is valuable because it often means:

lower memory use,
fewer allocations,
better cache behavior,
and stronger interview complexity.

It is also risky because you can destroy information that later steps still need.

2.7 Common iteration patterns

Arrays show up in a small set of recurring movement patterns:

left-to-right scan,
right-to-left scan,
two pointers moving inward,
fast/slow pointer,
read pointer + write pointer,
nested loops for pair checks,
prefix accumulation,
window expansion and shrinkage.

This topic stays at the fundamentals, but these patterns start here.

2.8 Default values in Java arrays

Java initializes array elements automatically.

Type	Default value
`int[]`	`0`
`long[]`	`0L`
`double[]`	`0.0`
`boolean[]`	`false`
`char[]`	`\u0000`
`String[]`	`null`
`Object[]`	`null`

This is convenient, but it can also hide bugs. A zero may mean “not set”, or it may be a real value. Good solutions do not confuse those states.

2.9 Array vs `ArrayList`

Interview candidates often mix up raw arrays and ArrayList.

Feature	Array	`ArrayList`
Size	Fixed	Resizable
Primitive storage	Yes	No
Index access	`O(1)`	`O(1)`
Memory overhead	Lower	Higher
Generics	No	Yes
Best for algorithm templates	Often	Sometimes

2.10 Recognition signals

Array thinking should trigger early when:

the input is a list of values,
positions matter,
order matters,
the problem mentions subarray, range, adjacent, prefix, or sorted input,
or a one-pass or two-pass scan looks plausible.

2.11 Invariants matter early

A strong array solution is rarely “just a loop”. It usually hides an invariant such as:

left and right always bound the unresolved region,
write marks the next kept position,
prefix[i] stores information about the first i items,
or currentMax summarizes everything seen so far.

If you can state the invariant, you can usually debug the solution much faster.

3. Practical Usage

When to use arrays

Arrays are strong when:

size is known up front,
performance matters,
the solution is index-driven,
you want low overhead,
primitives matter,
or you are writing an interview-style solution with clean complexity.

Typical examples:

sum or average,
maximum or minimum,
reverse in place,
move zeroes,
remove duplicates from sorted input,
rotate values,
count frequencies in a small fixed domain.

When arrays are especially good in LeetCode

Arrays shine when constraints are large. If n is up to 10^5 or 10^6, a single linear pass can already be a strong answer. That is often exactly the kind of reasoning interviewers want to hear.

When NOT to use raw arrays

Raw arrays are weaker when:

size changes frequently,
you need key-based lookup,
you need frequent middle insertion,
you need sorted-key navigation,
or collection APIs improve clarity enough to justify overhead.

Then you may want ArrayList, HashMap, Deque, TreeMap, or another structure.

Java-specific guidance

Prefer arrays when:

solving algorithm problems,
using primitive values,
building helper arrays such as prefix, visited, dp, or count,
or keeping the implementation compact matters.

Prefer ArrayList when:

the final size is unknown,
resizing matters,
or collection-based APIs make the code cleaner.

Pair-programming perspective

Arrays are easy to explain aloud. Good narration sounds like this:

“I will scan left to right.”
“I will keep a running maximum.”
“I will use one read pointer and one write pointer.”
“This stays in-place, so extra space is O(1).”

That style of explanation is useful both in pair programming and in interviews because it shows control over the algorithm, not just syntax.

Practical checklist before coding

Before settling on an array solution, ask:

Do I need the original order?
Can I modify the input?
Is extra memory acceptable?
Is the input sorted?
Is this really a scanning problem?
What invariant can I keep while moving through the array?

Common early transforms

A stronger solution often begins with one of these transforms:

sort first,
build a prefix array,
count values,
compact in place,
reverse a suffix,
precompute left/right information.

These are not "different worlds". They are extensions of solid array fundamentals.

LeetCode #26 — Remove Duplicates from Sorted Array — classic in-place compaction with write pointer.
LeetCode #283 — Move Zeroes — invariant-based in-place rearrangement.
LeetCode #189 — Rotate Array — reverse-based rotation technique.
LeetCode #344 — Reverse String — two-pointer swap pattern.
LeetCode #88 — Merge Sorted Array — backward fill to avoid extra space.

4. Code Examples

Basic Example — scan and aggregate

import java.util.Arrays;

public class ArraySumExample {
    public static int sum(int[] nums) {
        int total = 0;
        for (int value : nums) {
            total += value;
        }
        return total;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 7, 2};
        System.out.println(sum(nums)); // 14
        System.out.println(Arrays.toString(nums)); // [4, 1, 7, 2]
    }
}

This example matters because it shows the most basic and most reusable array skill: scanning once with O(n) time and O(1) extra space.

Basic Example — direct update

import java.util.Arrays;

public class ArrayUpdateExample {
    public static void main(String[] args) {
        int[] scores = {10, 20, 30, 40};
        scores[2] = 99;
        System.out.println(Arrays.toString(scores));
    }
}

This is small, but it demonstrates the direct write power of arrays.

Advanced Example — reverse in place

import java.util.Arrays;

public class ReverseArrayExample {
    public static void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        reverse(nums);
        System.out.println(Arrays.toString(nums)); // [5, 4, 3, 2, 1]
    }
}

What this teaches:

arrays work well with pointer-based movement,
no second array is needed,
extra space remains O(1).

Advanced Example — remove duplicates from sorted array

import java.util.Arrays;

public class RemoveDuplicatesExample {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[read - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 4, 4};
        int length = removeDuplicates(nums);
        System.out.println(length); // 4
        System.out.println(Arrays.toString(Arrays.copyOf(nums, length))); // [1, 2, 3, 4]
    }
}

This is a classic interview example because it converts “array basics” into read/write pointer discipline.

Common Pitfall — off-by-one

public class OffByOneExample {
    public static int lastElement(int[] nums) {
        return nums[nums.length - 1];
    }
}

A common wrong version is:

// ❌ Out of bounds
int value = nums[nums.length];

Reason:

length is the count,
the last valid index is length - 1.

Common Pitfall — unsafe neighbor access

public class NeighborCheckExample {
    public static boolean hasEqualNeighbors(int[] nums, int index) {
        if (index < 0 || index >= nums.length - 1) {
            return false;
        }
        return nums[index] == nums[index + 1];
    }
}

This is a small but realistic example of why boundary thinking matters.

Review-style explanation

For the removeDuplicates example, a strong explanation is:

the array is sorted,
read scans every element,
write marks where the next distinct value should go,
values before write are always the compacted distinct prefix,
and the returned length tells the caller which part of the array is now valid.

That is both algorithmic reasoning and pair-programming communication.

5. Trade-offs

Aspect	Details
⚡ Performance	Excellent for indexed access and linear scans; weak for frequent middle insertion or deletion because elements shift.
💾 Memory	Very compact for primitives and usually leaner than collection-based alternatives.
🔧 Maintainability	Simple model, but index-heavy logic becomes fragile when invariants are not named clearly.
🔄 Flexibility	Low flexibility because size is fixed; resizing means new allocation and copying.

Performance trade-off in plain words

Arrays are fast when you move through them predictably. They are not magic. They become a poor fit when the workload constantly reshapes the middle.

Memory trade-off

An int[] is usually much cheaper than List<Integer> because List<Integer> introduces boxing and object overhead. In algorithmic work, that difference can matter a lot.

Simplicity trade-off

Arrays look simple at first, but multi-index solutions can become brittle. Good variable names such as left, right, read, write, prefix, and currentMax reduce that risk.

Safety trade-off

Java arrays are safer than raw memory because they enforce bounds checking. That is good for correctness, but it also means sloppy indexing fails fast.

Interview trade-off

Sometimes a non-array structure is conceptually prettier, but the array solution wins because:

it is easier to explain,
it uses less memory,
and it keeps the performance model obvious.

A good candidate can state that trade-off instead of blindly preferring one structure.

6. Common Mistakes

Confusing length with last index
Candidates write nums[nums.length] instead of nums[nums.length - 1]. The fix is to say the valid index range out loud: 0 through length - 1.
Ignoring the empty-array case
Code that touches nums[0] or nums[nums.length - 1] without checking nums.length == 0 will break on empty input.
Overwriting needed information during in-place updates
In-place saves memory, but bad pointer strategy can destroy data you still need. Sometimes direction matters; sometimes a temporary variable matters.
Using nested loops too early
Beginners often jump to O(n^2) before asking whether one scan, one state variable, or a simple transform is enough.
Weak naming for index-heavy logic
If everything is i, j, and k, reasoning becomes fragile. Role-based names make bugs easier to spot.
Ignoring sorted-input leverage
A sorted array is often the signal that better patterns are available: two pointers, binary search, or in-place duplicate compression.
Mixing up arrays and ArrayList behavior
Arrays do not grow automatically. “Need more capacity” means “allocate another array”.
Forgetting to state the invariant
The code may still work, but if you cannot describe what is guaranteed after each step, debugging and explaining become much harder.

7. Deep Dive

How experienced engineers think about arrays

Senior engineers do not stop at O(1) access. They think about memory layout, cache locality, mutation cost, boxing overhead, and what later optimization paths become possible because the data is indexable and compact.

Cache locality matters

Arrays are often fast not only because of asymptotic complexity, but because sequential access is cache-friendly. That is one reason array-based structures frequently beat pointer-heavy alternatives in real workloads.

Bounds checking in Java

Every array access in Java is checked. That is part of the language safety model. From an interview perspective, it means your boundary logic must be explicit and trustworthy, especially around left + 1, right - 1, or mid calculations.

Primitive arrays vs boxed values

int[] and Integer[] behave very differently. Primitive arrays store raw values; boxed arrays store references to objects. That affects memory usage, cache behavior, nullability, and runtime cost. For most algorithm problems, primitive arrays are the better baseline.

Why arrays unlock later patterns

Almost every early DSA pattern depends on three array habits: index awareness, invariant awareness, and edge-case awareness. If those habits are weak, later topics feel random. If they are strong, later patterns feel like natural extensions.

Interview explanation example

A clean explanation might sound like this:

“I keep the data in the original array.”
“I solve it in one pass, so time is O(n).”
“I only use a few variables, so extra space is O(1).”
“The risky part is boundary handling at the first and last indices.”
“If the input were sorted, I would consider two pointers next.”

That is the kind of calm, explicit narration that works well in pair programming and interviews.

Why this topic matters beyond itself

Arrays are not only a standalone topic. They are the platform for two pointers, sliding window, prefix sums, binary search on positions, many DP tables, and most frequency or counting helpers. So if array basics feel shaky, many later topics feel harder than they actually are.

8. Interview Questions

Q: Why is array index access O(1)?
A: Because the location of an element can be computed directly from the base position and the index, so the algorithm does not traverse earlier elements.

Q: Why is inserting into the middle of an array usually O(n)?
A: Because elements after the insertion point must shift to make room, and that movement dominates the cost.

Q: What does in-place mean in an interview answer?
A: It means the solution works on the original structure instead of allocating another full-sized structure, often targeting O(1) extra space.

Q: When would you choose an array over ArrayList in Java?
A: When size is known, primitive performance matters, and index-based logic is central to the solution.

Q: What are the first edge cases to check in an array problem?
A: Empty input, single-element input, first index, last index, duplicates, already-sorted input, and all-equal values.

Q: What is a good invariant for a compacting array algorithm?
A: A common one is: everything before write is already processed and in final kept form, while everything from read onward is still unresolved.

9. Glossary

Term	Definition
contiguous memory	Elements are stored next to each other in a compact block.
index	Zero-based position used to access an element.
in-place	Modifying the original structure without allocating another full-sized structure.
bounds checking	Runtime validation that an index stays in valid range.
boxing	Wrapping a primitive value like `int` into an object like `Integer`.
cache locality	Performance advantage from nearby memory being accessed together.
read pointer	The index currently used to inspect values.
write pointer	The index where the next kept or transformed value should be stored.
invariant	A condition that remains true throughout the algorithm and helps prove correctness.

10. Cheatsheet

Arrays are fixed-size, contiguous, index-based structures.
Read and write by index are usually O(1).
Full scan is O(n).
Middle insertion and deletion are usually O(n) because of shifting.
Last valid index is length - 1.
In-place often means O(1) extra space.
Empty-array handling should be one of your first checks.
Primitive arrays are often better than boxed alternatives for algorithm work.
Sorted arrays often unlock better patterns.
State the invariant if you want the solution to be easy to review and debug.
Strong array fundamentals make later DSA topics much easier.