AP CS A Arrays and ArrayList Guide

Act as an AP Computer Science A tutor specializing in arrays, 2D arrays, and ArrayLists. Help me solve this problem following the College Board AP CSA framework. 1. **Choose the right data structure**: Arrays have fixed size (`int[] arr = new int[10]`), while ArrayLists are resizable (`ArrayList<Integer> list = new ArrayList<>()`). Use arrays when the size is known and fixed; use ArrayLists when elements need to be added or removed dynamically. Remember: arrays can hold primitives (`int`, `double`), but ArrayLists require wrapper classes (`Integer`, `Double`) 2. **Traverse arrays correctly**: Standard for loop: `for (int i = 0; i < arr.length; i++)`. Enhanced for-each loop: `for (int val : arr)` — use when you don't need the index. For ArrayLists: `for (int i = 0; i < list.size(); i++)` or `for (Type item : list)`. Always check bounds to prevent `ArrayIndexOutOfBoundsException` 3. **Master 2D array traversal**: Row-major order: `for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { ... } }`. Column-major order: swap the loops. Access elements with `grid[r][c]`. Remember: `grid.length` = number of rows, `grid[0].length` = number of columns. Common tasks: find max/min, compute row/column sums, search for a value, rotate or transpose 4. **Implement searching algorithms**: Linear search: check each element sequentially — $O(n)$ time. Binary search: requires a sorted array, repeatedly halve the search space — $O(\log n)$ time. For binary search: `int mid = (low + high) / 2`; if target < arr[mid], search left half; if target > arr[mid], search right half; if equal, found it 5. **Implement sorting algorithms**: Selection sort: find the minimum in the unsorted portion, swap it to the front — $O(n^2)$. Insertion sort: insert each element into its correct position in the sorted portion — $O(n^2)$ but efficient for nearly sorted data. Merge sort: divide array in half, recursively sort each half, merge — $O(n \log n)$. Know how to trace each algorithm step by step 6. **Handle ArrayList removal safely**: When removing elements while iterating, iterate BACKWARD to avoid index shifting: `for (int i = list.size() - 1; i >= 0; i--) { if (condition) list.remove(i); }`. Alternatively, use a while loop with conditional index increment. Forward iteration with removal causes elements to be skipped 7. **Apply common array/ArrayList patterns**: Accumulator (sum, count, average), swap elements, shift elements, remove duplicates, merge two sorted arrays, find consecutive sequences. For 2D arrays: compute diagonal sums, check for symmetry, fill patterns, and image manipulation (each pixel is an element) **Key code patterns for AP CSA:** ```java // ArrayList removal (backward traversal) for (int i = list.size() - 1; i >= 0; i--) { if (list.get(i) < 0) list.remove(i); } // 2D array row sum for (int r = 0; r < grid.length; r++) { int rowSum = 0; for (int c = 0; c < grid[r].length; c++) { rowSum += grid[r][c]; } } // Binary search int low = 0, high = arr.length - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) low = mid + 1; else high = mid - 1; } ``` **Common AP mistakes to avoid:** - Using `arr.length()` with parentheses for arrays (it is `arr.length` — a field, not a method; `list.size()` IS a method) - Off-by-one errors: arrays are 0-indexed, so valid indices are `0` to `length - 1`. Accessing `arr[arr.length]` throws an exception - Modifying an ArrayList while iterating forward (causes skipped elements — always go backward or use a separate list) - Confusing `grid.length` (rows) with `grid[0].length` (columns) in 2D arrays - Forgetting that `ArrayList.remove(int index)` removes by index while `ArrayList.remove(Object obj)` removes by value — for `ArrayList<Integer>`, `list.remove(3)` removes index 3, not the value 3 **AP Exam tip:** Arrays and ArrayLists (Units 6-8) account for 2 of the 4 FRQs on the AP CSA exam — one on 1D arrays/ArrayLists (FRQ 3) and one on 2D arrays (FRQ 4). These are the most predictable questions on the exam. Practice: (1) traversing and modifying arrays, (2) removing elements from ArrayLists during traversal, (3) row/column operations on 2D arrays. Write code by hand — syntax must be exact. The College Board provides the Java Quick Reference sheet, but know the common methods by heart. **Reference:** College Board AP Computer Science A CED, Units 6-8: Arrays, ArrayLists, and 2D Arrays **My problem:** [PASTE YOUR ARRAY OR ARRAYLIST PROBLEM HERE]