ArrayLists in Java for Competitive Programming

What are ArrayLists in Java?

An ArrayList in Java is a resizable array implementation of the List interface. Unlike arrays, which have a fixed size determined at the time of creation, ArrayLists can dynamically grow or shrink as elements are added or removed. This makes them incredibly versatile for scenarios where the number of elements is unknown or changes frequently. They are part of the java.util package, so you'll need to import them: import java.util.ArrayList;.

Exploring ArrayLists in Java

Dynamic Resizing

The key advantage of an ArrayList is its ability to resize automatically. When you add an element to a full ArrayList, it creates a new, larger array and copies the existing elements over. This process happens behind the scenes, freeing you from manually managing array sizes. While resizing has a time complexity of O(n), it's amortized over many operations, resulting in an average insertion time complexity of O(1) for adding elements at the end.

Example:

 import java.util.ArrayList;

public class ArrayListResizeExample {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            numbers.add(i);
            System.out.println("Size: " + numbers.size() + ", Capacity: " + getCapacity(numbers)); //Capacity is not directly accessible
        }
    }

    //A hacky way to estimate capacity - Don't rely on this in real code.
    private static int getCapacity(ArrayList l) {
        try {
            java.lang.reflect.Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(l)).length;
        } catch (NoSuchFieldException e) {
            return -1; // or other sentinel value
        } catch (IllegalAccessException e) {
            return -2; //or other sentinel value
        }
    }
} 

Insertion

You can insert elements into an ArrayList at specific positions using the add(int index, E element) method. This shifts existing elements to make room for the new one. Insertion at the beginning of an ArrayList is O(n) due to the shifting of elements. Adding to the end (add(E element)) is generally O(1) amortized.

Example:

 import java.util.ArrayList;

public class ArrayListInsertion {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add(1, "Charlie"); // Inserts "Charlie" at index 1, shifting "Bob" to index 2
        System.out.println(names); // Output: [Alice, Charlie, Bob]
    }
} 

Deletion

Elements can be removed from an ArrayList using the remove(int index) or remove(Object obj) methods. Removing an element at a specific index also involves shifting subsequent elements, resulting in O(n) time complexity. Removing by object searches for the first occurrence of the object and removes it, also typically O(n) in the worst case.

Example:

 import java.util.ArrayList;

public class ArrayListDeletion {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.remove(1); // Removes "Bob" at index 1
        System.out.println(names); // Output: [Alice, Charlie]

        names.remove("Alice"); // Removes the object "Alice"
        System.out.println(names); // Output: [Charlie]
    }
} 

Searching

ArrayLists provide the contains(Object obj) method to check if an element exists and the indexOf(Object obj) method to find the index of the first occurrence of an element. Both methods have a time complexity of O(n) as they may need to iterate through the entire list. For faster searching in sorted ArrayLists, consider using binary search (Collections.binarySearch()), which has a time complexity of O(log n), but requires the list to be sorted first.

Example:

 import java.util.ArrayList;
import java.util.Collections;

public class ArrayListSearching {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        System.out.println(numbers.contains(20)); // Output: true
        System.out.println(numbers.indexOf(30)); // Output: 2

        Collections.sort(numbers); // Sort for binary search
        int index = Collections.binarySearch(numbers, 20);
        System.out.println("Binary Search Index: " + index); //Output: Binary Search Index: 1

    }
} 

Advantages of ArrayLists over Arrays in Competitive Programming

In competitive programming, the dynamic resizing of ArrayLists is a significant advantage over arrays in several situations:

• Unknown Input Size: When the size of the input is not known beforehand, using a fixed-size array becomes problematic. ArrayLists allow you to accommodate the input regardless of its size.
• Frequent Insertions/Deletions: Problems involving frequent insertion or deletion of elements, especially in the middle of the sequence, are much easier to solve with ArrayLists. Arrays would require manual shifting of elements, leading to complex and potentially error-prone code.
• Simplicity and Readability: ArrayLists provide a more concise and readable syntax for common operations like adding, removing, and searching elements. This can save time and reduce the likelihood of bugs during a contest.

However, it's important to remember that ArrayLists have a slight performance overhead compared to arrays due to the dynamic resizing and the object-oriented nature of Java. If the size of the data is known beforehand and performance is absolutely critical, arrays might be a better choice. But for most cases, the convenience and flexibility of ArrayLists outweigh the performance difference.

Competitive Programming in Java with Solutions

Problem 1: Dynamic Array Sum

Problem Statement: You are given a series of integers as input. The number of integers is not known in advance. Store the integers in a dynamic array and calculate their sum.

 import java.util.ArrayList;
import java.util.Scanner;

public class DynamicArraySum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();

        // Read integers until there are no more inputs (e.g., end-of-file or a specific sentinel value).
        while (scanner.hasNextInt()) { //Using scanner.hasNextInt to check for more numbers.
            numbers.add(scanner.nextInt());
        }

        int sum = 0;
        for (int number : numbers) {
            sum += number;
        }

        System.out.println("Sum: " + sum);
        scanner.close();
    }
} 

Problem 2: Remove Duplicates

Problem Statement: Given a list of strings, remove all duplicate strings while preserving the original order.

 import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;

public class RemoveDuplicates {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<String> inputList = new ArrayList<>();

        // Read the number of strings to input.
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume the newline character after reading the integer.

        // Read each string and add it to the list.
        for (int i = 0; i < n; i++) {
            inputList.add(scanner.nextLine());
        }

        // Use LinkedHashSet to remove duplicates and preserve order.
        Set<String> uniqueStrings = new LinkedHashSet<>(inputList);
        ArrayList<String> resultList = new ArrayList<>(uniqueStrings); //Convert back to ArrayList

        System.out.println(resultList);
        scanner.close();
    }
} 

Problem 3: Finding the Kth Largest Element

Problem Statement: Given an unsorted array of integers, find the kth largest element in it.

 import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class KthLargestElement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();

        // Input array size and K
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // Reading in the array elements
        for (int i = 0; i < n; i++) {
            numbers.add(scanner.nextInt());
        }

        // Using min-heap of size k for efficiency
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : numbers) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        System.out.println("The " + k + "th largest element is: " + minHeap.peek());
        scanner.close();
    }
}