Complete Java for DSA: Collections, Arrays, Strings & Traps

Your logic is perfect. Your code still fails. Not because of the algorithm, but because of Java. Two numbers that look equal, but aren't. A sum that suddenly turns negative. A loop that looks fast, but takes forever.

These bugs fail more coding interviews than hard algorithms do. And by the end of this video, you'll know every one of them, and exactly how to avoid it.

Welcome back to Compiled Canvas. This is Episode Four of our DSA series. In Episode Three, we learned to calculate the complexity of any code. Today, we set up our toolkit: Java, the way you actually use it in DSA.

Here's the plan. Primitive types, and the overflow bug. Arrays, and the methods you'll use every day. Strings, and why they can't change. Wrapper classes, and the equals trap. Then the collections: ArrayList, HashMap and HashSet, TreeMap and TreeSet, stacks and queues with ArrayDeque, and the PriorityQueue. Sorting with comparators. A cheat sheet for which collection to pick. And a quiz at the end, with three bugs that catch almost everyone. And for every method, I'll tell you its time complexity.

Let's go.

First, the primitive types. The ones you'll use most are int, long, char, boolean and double.

An int holds whole numbers up to about two point one billion. That sounds like a lot, until it isn't. A long holds numbers up to about nine quintillion. Nine followed by eighteen zeros.

Here's the bug. Two billion plus two billion, in an int, does not give four billion. It gives a negative number. The value goes past the maximum, and wraps around to the bottom. That's called integer overflow. And Java won't warn you. No error, no crash. Just a wrong answer.

So when do you use long? When you add up many numbers, when you multiply two big numbers, or when the problem says the answer can be very large. A simple rule: if two values can each be close to a billion, their sum or product needs a long.

You'll also see this in binary search. Writing low plus high, divided by two, can overflow when both are large. The safe way is low plus, high minus low, divided by two.

And when a problem says return the answer modulo ten to the nine plus seven, that's a hint that the real answer is huge. Use long, and take the modulo at every step.

Now, char. A char is really a small number. So you can do arithmetic with it. The letter c minus the letter a gives two. That one trick turns any lowercase letter into an index from zero to twenty-five, and you'll use it in hundreds of string problems.

And double? Avoid it for exact answers. Decimal numbers can't always be stored exactly, so zero point one plus zero point two is not exactly zero point three. Use int or long whenever you can.

Next, arrays. An array is a fixed-size block of values, all of the same type, sitting next to each other in memory.

You create one with new int, and the size. Every slot starts at a default value: zero for numbers, false for booleans, and null for objects. And the size can never change. If you need more space, you create a new, bigger array.

Reading or writing any index is O of one, because Java can jump straight to it. Use an index outside the array, and you get the famous ArrayIndexOutOfBoundsException.

One small detail that trips people up: for an array, length is a field, with no brackets. For a string, length is a method, with brackets. And for a list, it's called size. Three different names for the same idea.

A two-dimensional array is an array of arrays. Grid of r, c means row r, column c. The number of rows is grid dot length, and the number of columns is grid of zero dot length. You'll use this for every matrix and grid problem.

Now, the Arrays class gives you the tools. Arrays dot sort sorts the array in O of n log n. Arrays dot fill sets every slot to one value, in O of n. Arrays dot toString turns the array into readable text, which is perfect for debugging. And Arrays dot copyOf, and copyOfRange, copy part of an array, in O of the length you copy.

And here's a trap. If you write int array b equals a, you don't get a copy. You get a second name for the same array. Change b, and a changes too. The same thing happens when you pass an array to a method: the method can change your original array. If you need a real copy, use Arrays dot copyOf, or clone.

Now, strings. The most important fact about a Java string is this: it can never change. It's immutable. Every method that seems to change a string actually creates a brand new one.

Here are the methods you'll use all the time. charAt gives you one character, in O of one. length gives the size. substring gives you a piece of the string, but it copies that piece, so it's O of the length of the piece, not O of one. And indexOf and contains search the string, which takes linear time.

Now, the equals trap. Never compare two strings with double equals. Double equals checks whether they're the same object in memory, not whether they have the same text. Two strings with the same letters can still be different objects. Always use dot equals. This one bug has failed countless interviews.

Next, building strings. Because strings can't change, adding to a string with plus inside a loop copies everything so far, every single time. Do that n times, and it's O of n squared. Instead, use a StringBuilder. Its append is O of one on average, so building the whole string is O of n. When you're done, call toString. And StringBuilder has a reverse method too, which is handy for palindrome problems.

Two more tools. To sort the letters of a word, turn it into a char array with toCharArray, sort that, and turn it back into a string. That's the classic way to check if two words are anagrams, in O of n log n.

And for counting letters, use a frequency array: an int array of size twenty-six. For each character, add one at index, character minus a. That counts every letter in a single pass, in O of n. And it's faster than a HashMap.

Now, wrapper classes. Collections like ArrayList and HashMap can only hold objects, not primitives. So Java gives every primitive an object version. int has Integer. long has Long. char has Character. boolean has Boolean.

Java converts between them for you. Putting an int into a list turns it into an Integer automatically. That's called autoboxing. Reading it back turns it into an int again. That's unboxing.

It's convenient, but it hides three traps.

Trap one: comparing Integers with double equals. Java caches small Integer values, from minus one twenty-eight to one twenty-seven. So two Integers holding one hundred are the same object, and double equals says true. But two Integers holding one thousand are different objects, and double equals says false. The same code, a different answer, just because the number got bigger. Always compare Integer objects with dot equals.

Trap two: null. If a HashMap doesn't have a key, get returns null. Store that in an int, and Java tries to unbox null, and throws a NullPointerException. Use getOrDefault instead.

Trap three: speed. Every boxed Integer is an object, with extra memory. An int array is much faster than a list of Integers. So when you know the size, prefer a plain array.

And a few helpers you'll use constantly. Integer dot MAX VALUE and Integer dot MIN VALUE, as infinity, when you're looking for a minimum or a maximum. Integer dot parseInt, to turn text into a number. And Character dot isDigit, isLetter, and toLowerCase, for string problems.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now, the collections. And we'll start with the one you'll use the most: ArrayList.

Write it like this: List of Integer, list equals new ArrayList. The type on the left is the interface, List. The type on the right is the actual class. That's the standard way to write it.

An ArrayList is an array that grows by itself. Adding to the end is O of one on average. Every so often it has to grow and copy everything, but averaged out, it's still constant time. Get and set by index are O of one.

But some methods are slow. Adding or removing in the middle, or at the front, is O of n, because every element after it has to shift. And contains, indexOf, and remove by value all scan the list, so they're O of n too.

And here's a trap that catches almost everyone. On a list of Integers, list dot remove of one does not remove the number one. It removes the element at index one. To remove the value one, you have to write list dot remove, Integer dot valueOf, one.

And one more. Never add or remove elements from a list while you're looping over it with a for-each loop. Java throws a ConcurrentModificationException. Loop over a copy, or use an index, or collect the changes and apply them afterwards.

To sort a list, use Collections dot sort, which is O of n log n. And to reverse it, Collections dot reverse, in O of n.

Next, the most powerful tool in all of DSA interviews: the HashMap.

A HashMap stores key and value pairs. put adds or updates a pair. get reads the value for a key. containsKey checks if a key exists. And remove deletes it. All of them are O of one, on average. That's why a HashMap turns so many O of n squared solutions into O of n.

The most common use is counting. For each number, put the number, with getOrDefault of the number and zero, plus one. In one line, that counts how many times every value appears.

To loop over a map, use entrySet. It gives you each key and its value together. But remember: a HashMap has no order. Don't expect the keys to come out sorted, or in the order you added them. If you need insertion order, use a LinkedHashMap.

A HashSet is a HashMap with only keys. add, contains and remove are all O of one on average. Use it to remove duplicates, or to answer "have I seen this before?" in constant time.

And a tip. If your keys are small numbers, or lowercase letters, a plain array is even faster than a HashMap. That's the frequency array trick again.

Sometimes you need fast lookups, and order. That's when you use a TreeMap or a TreeSet.

A TreeMap keeps its keys sorted at all times. put, get, and remove are O of log n. A little slower than a HashMap, but now the keys are in order.

And it gives you superpowers that a HashMap doesn't have. firstKey and lastKey give you the smallest and the largest key. floorKey of x gives you the largest key less than or equal to x. And ceilingKey of x gives you the smallest key greater than or equal to x. All in O of log n.

So whenever a problem says "the closest value", "the next larger", or "the smallest one above", think TreeMap or TreeSet.

A TreeSet is the same idea, with only keys. It keeps unique values in sorted order, with first, last, floor and ceiling.

Now, stacks and queues. In Java, use one class for both: ArrayDeque.

As a stack, last in, first out: push adds to the top, pop removes from the top, and peek looks at the top. All O of one. You'll use stacks for brackets, undo operations, and for depth-first search.

As a queue, first in, first out: offer adds to the back, poll removes from the front, and peek looks at the front. All O of one. You'll use queues for breadth-first search, and level order traversal.

Avoid the old Stack class. It's slower, because it was built for multiple threads. ArrayDeque is the modern choice.

And then there's the PriorityQueue. It always gives you the smallest element first. offer adds an element in O of log n. poll removes the smallest in O of log n. And peek looks at the smallest in O of one.

By default, it's a min-heap. For a max-heap, pass Collections dot reverseOrder when you create it.

Whenever a problem says "top k", "k largest", "k smallest", or "keep getting the minimum", think PriorityQueue. And building one from a whole list at once is just O of n.

Next, custom sorting. Very often you'll sort pairs, like intervals, by their start.

For an array of int arrays, write Arrays dot sort, the array, and a comparator: a comma b, arrow, Integer dot compare, a of zero, b of zero. That sorts the intervals by their first value, in O of n log n.

Notice we used Integer dot compare, and not a of zero minus b of zero. Subtracting can overflow when the numbers are large, and then your sort silently breaks. Integer dot compare is always safe.

And one more limit. You can't pass a custom comparator to a plain int array. To sort numbers in a custom order, like descending, use an Integer array, or a list.

So, which one do you pick? Here's the cheat sheet. Pause and screenshot this.

Need fast access by index? An array, or an ArrayList. Need to look things up, or count them, fast? A HashMap, or a HashSet. Need the keys in sorted order, or the closest value? A TreeMap, or a TreeSet. Need last in, first out? An ArrayDeque, used as a stack. Need first in, first out? An ArrayDeque, used as a queue. Need the smallest or largest, again and again? A PriorityQueue.

Picking the right collection is half of the solution. The algorithm is often just a loop around it.

Okay, quiz time. Three snippets, three bugs. Pause the video, work out what each one prints, and then hit play.

Question one. Integer a equals one thousand, Integer b equals one thousand. Print a, double equals, b.

Question two. A list of Integers holding ten, twenty and thirty. Call list dot remove of one. What's left in the list?

Question three. int big equals two billion. Print big plus big.

Ready?

Question one: false. One thousand is outside the cache, so a and b are two different objects. Use a dot equals b.

Question two: ten and thirty. remove of one removed the element at index one, which was twenty, not the number one.

Question three: a negative number, minus two hundred ninety-four million, nine hundred sixty-seven thousand, two hundred ninety-six. The sum overflowed. Use long.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. Use long when sums or products can get big, because int overflows silently. Arrays are fixed size, with O of one access, and the Arrays class to sort, fill and print them. Strings can't change. Compare them with equals, and build them with a StringBuilder. Wrapper classes box your numbers. Compare Integers with equals, and watch out for null. ArrayList for lists, HashMap and HashSet for fast lookups, TreeMap and TreeSet for order, ArrayDeque for stacks and queues, and the PriorityQueue for the smallest or largest. And sort with Integer dot compare, never with subtraction.

Your homework. Solve Valid Anagram twice. First by sorting both strings, then with a frequency array of size twenty-six. Write the time complexity of each. Then tell me in the comments: which collection would you use to find the k largest numbers in an array?

Next episode, we cover the math you need for DSA. Primes, GCD, modulo arithmetic, and the Sieve of Eratosthenes, the fastest way to find every prime up to n.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.