Day 1: Arrays — Foundation of Data Structures

15 Days of Data Structures and Algorithms

Photo by Nik Volkov on Unsplash

What is an Array?

An array is a collection of elements, all of the same type, stored in contiguous memory locations. It allows random access to elements using an index and is one of the most fundamental data structures in programming.

Characteristics:

1. Fixed Size: Once declared, the size of an array cannot be changed.
2. Homogeneous Elements: All elements in the array must be of the same type.
3. Contiguous Memory: Elements are stored in consecutive memory locations.
4. Zero-based Indexing: The first element is accessed using index 0.

Array Operations:

1. Traverse: Access and process each element.
2. Insertion: Add elements at a specific position.
3. Deletion: Remove elements from a specific position.
4. Search: Find the position of an element.
5. Update: Modify an element at a specific index.

Time and Space Complexities of Array Operations:

• Access: O(1)
• Search: O(n)
• Insertion: O(n) (shifting elements required unless adding at the end)
• Deletion: O(n) (shifting elements required)
• Space Complexity: O(n)

Trade-offs and Use Cases:

• Use arrays when you need fast access by index and the size of the collection is known in advance.
• Consider alternatives like ArrayList or LinkedList when dynamic resizing or frequent insertions/deletions are needed.

Common Mistakes:

1. Array Index Out of Bounds: Ensure indices are within the valid range (0 to array.length-1).
2. Incorrect Traversal Logic: Off-by-one errors, especially in loops.
3. Overwriting Data: When inserting/deleting, ensure no unintended overwrites occur.

Implementation in Java

Declaring and Initializing Arrays:

// Declaration
int[] numbers = new int[5];

// Initialization
numbers[0] = 10;
numbers[1] = 20;

// Declaration and initialization together
int[] ages = {25, 30, 35, 40};

Traversing an Array:

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

// Using enhanced for-loop
for (int num : ages) {
    System.out.println(num);
}

Common Operations:

Insertion: Add an element at a specific position.

int[] arr = {1, 2, 4, 5};
int pos = 2; // Index to insert at
int element = 3;


for (int i = arr.length - 1; i > pos; i--) {
    arr[i] = arr[i - 1];
}

arr[pos] = element;

Deletion: Remove an element from a specific position.

int[] arr = {1, 2, 3, 4, 5};
int pos = 2; // Index to delete

for (int i = pos; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
}

arr[arr.length - 1] = 0; // Optional: reset last element

Java-Specific Insights

Array vs ArrayList:

1. Arrays have a fixed size; ArrayList can dynamically resize.
2. ArrayList provides utility methods like add(), remove(), and contains(), which arrays lack.

Useful Java Features:

• Comparator and Comparable: Use for custom sorting.

Arrays.sort(arr, (a, b) -> a - b); // Lambda expression for ascending order

• Streams API: Simplify array operations.

int sum = Arrays.stream(arr).sum();

Popular Interview Questions

1. Find the Maximum Product Subarray

Problem Statement: Given an array, find the contiguous subarray within it that has the maximum product.

Solution:

public int maxProduct(int[] nums) {
    int maxProduct = nums[0];
    int currentMax = nums[0];
    int currentMin = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int temp = currentMax;
        currentMax = Math.max(nums[i], Math.max(currentMax * nums[i], currentMin * nums[i]));
        currentMin = Math.min(nums[i], Math.min(temp * nums[i], currentMin * nums[i]));

        maxProduct = Math.max(maxProduct, currentMax);
    }
    return maxProduct;
}

2. Rotate an Array by k Steps

Problem Statement: Rotate an array to the right by k steps.

Solution:

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

Practice Questions

1. Find the largest sum contiguous subarray (Kadane’s Algorithm).
2. Merge two sorted arrays.
3. Find all pairs in an array that sum up to a given value.
4. Move all zeros to the end of the array.
5. Find the missing number in an array of size n-1 containing numbers from 1 to n.
6. Check if an array contains duplicate elements.
7. Find the maximum difference between two elements such that the larger element appears after the smaller one.
8. Implement a function to reverse an array.
9. Find the “leader” elements in an array (an element is a leader if all elements to its right are smaller).
10. Implement matrix rotation by 90 degrees using arrays.