Arrays and Strings

Arrays and Strings

Now that you've finished Introduction to Data Structures and Algorithms, you already have the interview lens: understand the data, reason about efficiency, and explain trade-offs.

Arrays and strings are where that lens starts paying off. In MAANG-style interviews, many problems begin with:

• a list of numbers: int[] nums
• a word or sentence: String s
• a need to scan, compare, count, or transform

Today we'll build practical Java intuition for these two structures without jumping ahead into linked lists, hashing, or advanced string algorithms.

An array is indexed storage

Think of an array as a row of numbered boxes.

index:   0    1    2    3    4
value: [10] [25] [30] [42] [99]

The key idea: if you know the index, Java can jump directly to that box.

That gives arrays their most important interview property:

• Read by index: fast
• Update by index: fast
• Search for an unknown value: may require scanning

So if someone asks, "Is 42 inside this array?", you usually need to inspect elements until you find it or reach the end.

Java array basics

In Java, arrays have a fixed length once created. You can change values inside the array, but you cannot directly resize the same array object.

Common operations:

• nums[i] reads or writes an element
• nums.length gives the number of elements
• valid indexes are 0 through nums.length - 1

Here is a small standalone example.

```java
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] scores = {91, 88, 76, 100};

        scores[1] = 95; // update index 1

        int sum = 0;
        for (int i = 0; i < scores.length; i++) {
            sum += scores[i];
        }

        double average = (double) sum / scores.length;

        System.out.println("Scores: " + Arrays.toString(scores));
        System.out.println("Average: " + average);
    }
}
```

You have this Java array:

int[] nums = {4, 8, 15, 16, 23, 42};

Which expression reads the value 16?

A string is an ordered sequence of characters

In Java, a String behaves like a read-only sequence of characters.

s = "code"
index:  0   1   2   3
char:   c   o   d   e

Useful methods:

• s.length() returns the number of characters
• s.charAt(i) reads the character at index i
• s.substring(a, b) returns characters from index a up to, but not including, b

Important Java detail: Strings are immutable. Operations like toUpperCase() create a new string instead of changing the original.

```java
public class Main {
    public static void main(String[] args) {
        String word = "java";
        String upper = word.toUpperCase();

        System.out.println("Original: " + word);
        System.out.println("Uppercase: " + upper);
        System.out.println("First character: " + word.charAt(0));
        System.out.println("Length: " + word.length());
    }
}
```

True or false?

In Java, calling word.toUpperCase() changes the original String word in place.

Interview pattern: scan once, track useful state

Many beginner array problems become easier when you ask:

What small piece of information should I remember while scanning?

Example: given daily stock prices, find the best profit from one buy followed by one sell.

We do not need to compare every pair. As we scan left to right, we track:

• the lowest price seen so far
• the best profit seen so far

This is the kind of efficiency thinking you practiced in the introduction lesson.

```java
public class Main {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};

        int minSoFar = prices[0];
        int bestProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            int todayPrice = prices[i];
            int profitIfSoldToday = todayPrice - minSoFar;

            bestProfit = Math.max(bestProfit, profitIfSoldToday);
            minSoFar = Math.min(minSoFar, todayPrice);
        }

        System.out.println("Best profit: " + bestProfit);
    }
}
```

Fill in the blank to loop over every valid index of this Java array:

for (int i = 0; i < ____; i++) {
    System.out.println(nums[i]);
}

Pattern: compare from both ends

For arrays and strings, another common move is to use two indexes.

For a palindrome check, compare:

r a c e c a r
^           ^
left      right

If the outer characters match, move inward. If they ever differ, the string is not a palindrome.

This pattern stays within today's scope: simple index movement over an array-like structure.

```java
public class Main {
    static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println("racecar: " + isPalindrome("racecar"));
        System.out.println("daily: " + isPalindrome("daily"));
    }
}
```

Watch for these mistakes

Arrays and strings look simple, but interviews often test careful indexing.

Common pitfalls:

• Using index length instead of length - 1
• Mixing up arr.length and s.length()
• Forgetting that strings are immutable in Java
• Creating unnecessary nested loops when one scan is enough
• Not handling empty arrays or one-character strings

A useful habit: before coding, say the valid index range out loud.

Array of length n => valid indexes: 0 to n - 1
String of length n => valid indexes: 0 to n - 1

What you should remember

You now have the first real DSA tools in your Java interview toolkit.

Arrays:

• store fixed-size indexed data
• allow fast access by index
• are often solved with scanning and careful state tracking

Strings:

• are indexed character sequences
• use length() and charAt(i)
• are immutable in Java

Patterns introduced today:

• single pass with remembered state
• two pointers from both ends
• careful boundary handling

Next, we'll move to Linked Lists, where the big shift is that elements are connected by references rather than direct indexes.