Array and String

Solution and explanation

Array

An array stores elements of the same type in contiguous (adjacent) memory locations, accessed by an index starting at 0. Because the address of element i is base + i × size, reading any element takes O(1).

index:   0    1    2    3    4
value: [ 12 | 45 | 7  | 23 | 56 ]
address: 1000 1004 1008 1012 1016   (4-byte ints)

int[] marks = {12, 45, 7, 23, 56};
System.out.println(marks[2]);        // 7  (O(1) access)
marks[2] = 70;                       // O(1) update
int sum = 0;
for (int m : marks) sum += m;        // O(n) traversal
System.out.println(sum);             // 206

Operation complexity

• Access/update by index: O(1).
• Search unsorted: O(n). Search sorted (binary search): O(log n).
• Insert/delete at the end of a dynamic array (ArrayList): amortised O(1).
• Insert/delete at the start or middle: O(n), because elements shift.

Static vs dynamic arrays

Java arrays have a fixed size. ArrayList grows by allocating a larger array (about 1.5×) and copying, which is why appends are amortised O(1).

String

A string is a sequence of characters. In Java, String is immutable: every "modification" creates a new object. Use StringBuilder when building strings in a loop.

String s = "ascendia";
System.out.println(s.length());          // 8
System.out.println(s.charAt(0));         // a
System.out.println(s.substring(0, 3));   // asc
System.out.println(s.indexOf("end"));    // 2

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) sb.append(i).append(',');
System.out.println(sb);                  // 0,1,2,

Note: s1 == s2 compares references; always compare string content with equals().

Common techniques for array/string problems

• Two pointers (from both ends or slow/fast).
• Prefix sums for range totals.
• Sliding window for subarrays/substrings.
• Hashing (HashMap/HashSet) for counts and lookups.
• Sorting first to simplify the problem.

Advantages and disadvantages

• O(1) random access, cache-friendly, low memory overhead.
• Fixed size (static arrays) and costly insertion/deletion in the middle.

Solution and explanation

Problem

Return true if the array is sorted in non-decreasing order.

[1, 2, 2, 5, 9] → true
[1, 4, 3, 5]    → false

Approach: compare neighbours (optimal)

If any element is smaller than the one before it, the array is not sorted.

static boolean isSorted(int[] a) {
    for (int i = 1; i < a.length; i++) {
        if (a[i] < a[i - 1]) return false;
    }
    return true;
}

Brute force for comparison

Copy and sort the array, then compare with the original: O(n log n) time, O(n) space – unnecessary work.

Recursive version

static boolean isSortedRec(int[] a, int n) {
    if (n <= 1) return true;
    return a[n - 1] >= a[n - 2] && isSortedRec(a, n - 1);
}

Complexity

• Neighbour check: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n) call stack.

Note: empty and single-element arrays are sorted; for strictly increasing use <= instead of <.

Solution and explanation

Problem

Reverse the elements of an array in place.

[1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]

Approach 1: extra array

Copy elements into a new array from the end. Time O(n), Space O(n).

Approach 2: two pointers (optimal)

Swap the first and last elements, move inwards, stop when the pointers meet.

static void reverse(int[] a) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        int temp = a[left];
        a[left++] = a[right];
        a[right--] = temp;
    }
}

Dry run

[1,2,3,4,5]: swap 1↔5 → [5,2,3,4,1]; swap 2↔4 → [5,4,3,2,1]; left == right → stop.

Complexity

• Extra array: O(n) time, O(n) space.
• Two pointers: O(n) time, O(1) space.

Note: the same idea reverses a string (on a char array), a range of an array (used in array rotation) or a linked list's values.

Solution and explanation

Problem

Rotate an array to the right by k steps.

[1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]

Approach 1: rotate one step k times

Move the last element to the front k times. Time O(n·k).

Approach 2: extra array

Place a[i] at index (i + k) % n in a new array. Time O(n), Space O(n).

static void rotateExtra(int[] a, int k) {
    int n = a.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) res[(i + k) % n] = a[i];
    System.arraycopy(res, 0, a, 0, n);
}

Approach 3: reversal algorithm (optimal)

1. Reverse the whole array.
2. Reverse the first k elements.
3. Reverse the remaining n − k elements.

static void rotate(int[] a, int k) {
    int n = a.length;
    k %= n;                              // k may be larger than n
    reverse(a, 0, n - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
}
static void reverse(int[] a, int l, int r) {
    while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}

Dry run (k = 3)

• Reverse all: [7,6,5,4,3,2,1]
• Reverse first 3: [5,6,7,4,3,2,1]
• Reverse rest: [5,6,7,1,2,3,4] ✓

Complexity

• One step at a time: O(n·k). Extra array: O(n) time, O(n) space. Reversal: O(n) time, O(1) space.

Solution and explanation

Problem

Print every contiguous subarray of an array.

[1, 2, 3] → [1] [1,2] [1,2,3] [2] [2,3] [3]

Counting them

For n elements there are n(n+1)/2 subarrays (choose a start i and an end j ≥ i). For n = 3 that is 6.

Approach: two loops for start and end

static void printSubarrays(int[] a) {
    for (int start = 0; start < a.length; start++) {
        StringBuilder sb = new StringBuilder("[");
        for (int end = start; end < a.length; end++) {
            sb.append(end > start ? "," : "").append(a[end]);
            System.out.println(sb + "]");
        }
    }
}

Output
[1]
[1,2]
[1,2,3]
[2]
[2,3]
[3]

Recursive version

static void subarrays(int[] a, int start, int end) {
    if (end == a.length) return;
    if (start > end) { subarrays(a, 0, end + 1); return; }
    System.out.println(Arrays.toString(Arrays.copyOfRange(a, start, end + 1)));
    subarrays(a, start + 1, end);
}

Complexity

• Generating all subarrays: O(n²) of them; printing each costs up to O(n), so O(n³) total output work; O(1) extra space besides the output.

Note: subarray (contiguous) ≠ subsequence (keeps order, may skip elements, 2^n of them) ≠ subset (order irrelevant). Most "maximum subarray" problems avoid enumeration using Kadane's algorithm or sliding windows.

Solution and explanation

Problem

Given an array with equal numbers of positive and negative integers, rearrange it so signs alternate, starting with a positive, keeping the relative order within each sign.

[3, 1, -2, -5, 2, -4] → [3, -2, 1, -5, 2, -4]

Approach 1: separate lists, then merge

Collect positives and negatives in order, then fill even indices with positives and odd indices with negatives. Two passes.

Approach 2: single pass with index pointers (optimal)

static int[] rearrange(int[] a) {
    int[] res = new int[a.length];
    int pos = 0, neg = 1;
    for (int x : a) {
        if (x > 0) { res[pos] = x; pos += 2; }
        else       { res[neg] = x; neg += 2; }
    }
    return res;
}

Dry run

3 → res[0]; 1 → res[2]; −2 → res[1]; −5 → res[3]; 2 → res[4]; −4 → res[5] → [3, −2, 1, −5, 2, −4].

Complexity

• Time O(n), Space O(n) for the result.

Variant: unequal counts

Alternate while both lists have elements, then append the leftovers in order.

Note: an in-place O(1)-space version exists but loses the relative order unless you use O(n²) rotations.

Solution and explanation

Problem

Given daily prices, choose one day to buy and a later day to sell to maximise profit. Return 0 if no profit is possible.

prices = [7, 1, 5, 3, 6, 4] → buy at 1, sell at 6 → profit 5
prices = [7, 6, 4, 3, 1]    → 0

Approach 1: try every pair (brute force)

static int maxProfitBrute(int[] p) {
    int best = 0;
    for (int i = 0; i < p.length; i++)
        for (int j = i + 1; j < p.length; j++) best = Math.max(best, p[j] - p[i]);
    return best;
}

Time O(n²).

Approach 2: track the minimum so far (optimal)

For each day, the best sale today uses the cheapest price seen before today.

static int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        best = Math.max(best, price - minPrice);
    }
    return best;
}

Dry run on [7, 1, 5, 3, 6, 4]

• 7: min 7, best 0
• 1: min 1, best 0
• 5: best 4
• 3: best 4
• 6: best 5
• 4: best 5 → answer 5

Complexity

• Brute force: O(n²) time. Optimal: O(n) time, O(1) space.

Follow-ups

• Unlimited transactions: add every positive day-to-day increase (greedy).
• At most two/k transactions or with cooldown/fees: dynamic programming.

Solution and explanation

Problem

An element is a leader if it is greater than or equal to every element to its right. The last element is always a leader.

[16, 17, 4, 3, 5, 2] → leaders 17, 5, 2

Approach 1: check every element (brute force)

For each i, scan all j > i. Time O(n²).

Approach 2: scan from the right with a running maximum (optimal)

static List<Integer> leaders(int[] a) {
    List<Integer> result = new ArrayList<>();
    int maxRight = Integer.MIN_VALUE;
    for (int i = a.length - 1; i >= 0; i--) {
        if (a[i] >= maxRight) {
            result.add(a[i]);
            maxRight = a[i];
        }
    }
    Collections.reverse(result);   // original left-to-right order
    return result;
}

Dry run

From the right: 2 (leader, max 2) → 5 (leader, max 5) → 3 → 4 → 17 (leader, max 17) → 16. Reversed: [17, 5, 2].

Complexity

• Brute force: O(n²). Right-to-left scan: O(n) time, O(1) extra space besides the output.

Solution and explanation

Problem

Check whether two strings are equal (same characters in the same order). Often asked together with "ignore case" and "same characters in any order (anagram)" variants.

Exact equality

static boolean same(String a, String b) {
    if (a == null || b == null) return a == b;
    if (a.length() != b.length()) return false;
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i)) return false;
    }
    return true;           // equivalent to a.equals(b)
}

Why not ==?

String x = "java";
String y = new String("java");
System.out.println(x == y);        // false – different objects
System.out.println(x.equals(y));   // true – same content

Ignoring case

a.equalsIgnoreCase(b), or compare Character.toLowerCase of each pair.

Same characters, any order (anagram)

Count characters with an int[26] (or a HashMap for Unicode): increment for a, decrement for b, then check all zeros.

static boolean sameChars(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < a.length(); i++) { count[a.charAt(i) - 'a']++; count[b.charAt(i) - 'a']--; }
    for (int c : count) if (c != 0) return false;
    return true;
}

Complexity

• Equality: O(n) time, O(1) space.
• Anagram by counting: O(n) time, O(1) space (26 counters). Sorting both strings instead costs O(n log n).

Solution and explanation

Problem

Reverse a string: "ascendia" → "aidnecsa".

Approach 1: StringBuilder

String reversed = new StringBuilder("ascendia").reverse().toString();

Approach 2: two pointers on a char array (in place)

static String reverse(String s) {
    char[] c = s.toCharArray();
    for (int l = 0, r = c.length - 1; l < r; l++, r--) {
        char t = c[l]; c[l] = c[r]; c[r] = t;
    }
    return new String(c);
}

Approach 3: recursion

static String reverseRec(String s) {
    if (s.length() <= 1) return s;
    return reverseRec(s.substring(1)) + s.charAt(0);
}

Easy to write but O(n²) because each substring and concatenation copies characters.

Avoid this

String r = "";
for (char ch : s.toCharArray()) r = ch + r;   // creates a new String each time → O(n²)

Complexity

• StringBuilder / two pointers: O(n) time, O(n) space for the new string.
• Recursive substring version: O(n²) time.

Variation: reverse the words of a sentence

"I love Java" → "Java love I": split on spaces, reverse the array of words, join.