Arrays

Q: Find the maximum subarray sum (Kadane's Algorithm)

Find the maximum subarray sum (Kadane's Algorithm) - A Medium difficulty question commonly asked at Amazon. Study Arrays patterns and Java implementation to solve this.

Q: Two Sum — find indices of two numbers that add to target

Two Sum — find indices of two numbers that add to target - A Easy difficulty question commonly asked at Google. Study Arrays patterns and Java implementation to solve this.

Q: Rotate array by k positions

Rotate array by k positions - A Medium difficulty question commonly asked at Microsoft. Study Arrays patterns and Java implementation to solve this.

Q: Find the duplicate number in an array of n+1 integers

Find the duplicate number in an array of n+1 integers - A Medium difficulty question commonly asked at Facebook. Study Arrays patterns and Java implementation to solve this.

Q: Merge two sorted arrays without extra space

Merge two sorted arrays without extra space - A Hard difficulty question commonly asked at Atlassian. Study Arrays patterns and Java implementation to solve this.

Beginner

The most fundamental data structure. Understand indexing, traversal, and the two-pointer technique used in 90% of array interview problems.

Think of it this way

Imagine the seats on a school bus — each has a number (0, 1, 2...). You can jump straight to seat 5 without checking any other seat first. That is O(1) access. But if a new student needs to squeeze into seat 3, everyone from seat 3 onwards has to shift one place back. That shuffling is why inserting in the middle costs O(n).

In code, it looks like thisJava

int[] seats = {10, 20, 30, 40, 50};

System.out.println(seats[2]);  // 30 — instant O(1), no looping
seats[2] = 99;                 // update in-place — also O(1)

// Dynamic size? Use ArrayList (backed by an array internally)
List<Integer> list = new ArrayList<>();
list.add(10);        // append to end — O(1) amortized
list.add(1, 99);     // insert at index 1 — O(n), shifts right

Overview

An array stores elements in contiguous memory locations, allowing O(1) random access by index. Arrays are fixed-size in most languages, but Java's ArrayList provides a dynamic resizable version backed by an array. Mastering arrays is non-negotiable — nearly every DSA problem involves array manipulation at some level.

Time & Space Complexity

Operation	Time	Space
Access by index	`O(1)`	`O(1)`
Search (unsorted)	`O(n)`	`O(1)`
Search (sorted, binary)	`O(log n)`	`O(1)`
Insert at end	`O(1) amortized`	`O(1)`
Insert at index	`O(n)`	`O(1)`
Delete at index	`O(n)`	`O(1)`

Java Implementation

Java

import java.util.Arrays;

public class ArrayPatterns {

    // Two-pointer: check if pair with target sum exists — O(n) after sort
    public static boolean hasPairWithSum(int[] arr, int target) {
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) return true;
            else if (sum < target) left++;
            else right--;
        }
        return false;
    }

    // Sliding window: max sum subarray of size k — O(n)
    public static int maxSumSubarray(int[] arr, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];
        int maxSum = windowSum;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }

    // Prefix sum: range sum query in O(1) after O(n) preprocessing
    public static int[] buildPrefixSum(int[] arr) {
        int[] prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    // Query sum from index l to r (inclusive) — O(1)
    public static int rangeSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l];
    }
}

Key Points to Remember

Use the two-pointer technique to solve problems in O(n) that naive solutions solve in O(n²)

int left = 0, right = arr.length - 1;
while (left < right) {
    // move pointers inward based on condition
    left++;  right--;
}

Sliding window pattern handles subarray/substring problems efficiently

// Slide a window of size k across the array — O(n)
windowSum += arr[i] - arr[i - k]; // add new element, drop oldest

Prefix sum arrays reduce range query time from O(n) to O(1)

prefix[i + 1] = prefix[i] + arr[i];          // build — O(n)
int rangeSum = prefix[r + 1] - prefix[l];    // query — O(1)

In Java, prefer int[] for primitives over Integer[] — avoids autoboxing overhead

Arrays.sort() uses dual-pivot quicksort for primitives, merge sort for objects

Arrays.sort(arr);                              // ascending
Arrays.sort(arr2, (a, b) -> b - a);           // descending (Integer[] only)

Interview Questions

Find the maximum subarray sum (Kadane's Algorithm)

MediumAmazonSolve it

Two Sum — find indices of two numbers that add to target

EasyGoogleSolve it

Rotate array by k positions

MediumMicrosoftSolve it

Find the duplicate number in an array of n+1 integers

MediumFacebookSolve it

Merge two sorted arrays without extra space

HardAtlassianSolve it

Ask Aria about Arrays

Your personal AI tutor — ask anything about this concept

All Topics

Linked List