Arrays in Java

Arrays are a fundamental data structure in Java and are widely used in Leetcode problems. Understanding their properties and operations is crucial for solving problems efficiently.

Table of Contents

1. Array Basics
2. Common Array Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

Array Basics

• Definition: An array is a fixed-size collection of elements of the same type.

• Declaration:

  int[] arr = new int[5]; // Array of size 5
  int[] arr = {1, 2, 3, 4, 5}; // Array initialization

• Indexing: Arrays are zero-indexed.

• Fixed Size: Once created, the size of an array cannot be changed.

Common Array Operations

1. Accessing Elements

• Syntax: arr[index]

• Example:

  int element = arr[0]; // Access first element

• Time Complexity: O(1)

• Space Complexity: O(1)

2. Updating Elements

• Syntax: arr[index] = value

• Example:

  arr[0] = 10; // Update first element

• Time Complexity: O(1)

• Space Complexity: O(1)

3. Length of an Array

• Method: arr.length

• Example:

  int len = arr.length; // len = 5

• Time Complexity: O(1)

• Space Complexity: O(1)

4. Iterating Through an Array

• Using For Loop:

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

• Using Enhanced For Loop:

  for (int num : arr) {
      System.out.println(num);
  }

• Time Complexity: O(n)

• Space Complexity: O(1)

5. Sorting an Array

• Method: Arrays.sort(arr)

• Example:

  Arrays.sort(arr); // Sorts the array in ascending order

• Time Complexity: O(n log n)

• Space Complexity: O(log n) (for sorting algorithm)

6. Searching in an Array

• Linear Search:

  for (int i = 0; i < arr.length; i++) {
      if (arr[i] == target) return i;
  }
  return -1;

  • Time Complexity: O(n)
  • Space Complexity: O(1)

• Binary Search (for sorted arrays):

  int index = Arrays.binarySearch(arr, target);

  • Time Complexity: O(log n)
  • Space Complexity: O(1)

7. Copying an Array

• Method: Arrays.copyOf(arr, length)

• Example:

  int[] newArr = Arrays.copyOf(arr, arr.length);

• Time Complexity: O(n)

• Space Complexity: O(n)

8. Filling an Array

• Method: Arrays.fill(arr, value)

• Example:

  Arrays.fill(arr, 0); // Fills the array with 0

• Time Complexity: O(n)

• Space Complexity: O(1)

Common Leetcode Patterns

1. Two Pointers

• Used for problems like two-sum, remove duplicates, etc.

• Example:

  int left = 0, right = arr.length - 1;
  while (left < right) {
      if (arr[left] + arr[right] == target) return new int[]{left, right};
      else if (arr[left] + arr[right] < target) left++;
      else right--;
  }
  return new int[]{-1, -1};

• Related Questions:

  • Two Sum
  • Remove Duplicates from Sorted Array
  • Container With Most Water

2. Sliding Window

• Used for problems like maximum subarray sum, minimum size subarray sum, etc.

• Example:

  int left = 0, sum = 0, maxLen = 0;
  for (int right = 0; right < arr.length; right++) {
      sum += arr[right];
      while (sum > target) {
          sum -= arr[left];
          left++;
      }
      maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;

• Related Questions:

  • Maximum Subarray
  • Minimum Size Subarray Sum
  • Longest Substring Without Repeating Characters

3. Prefix Sum

• Used for problems like subarray sum equals K, range sum queries, etc.

• Example:

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

• Related Questions:

  • Subarray Sum Equals K
  • Range Sum Query - Immutable
  • Continuous Subarray Sum

4. Binary Search on Arrays

• Used for problems like search in rotated sorted array, find peak element, etc.

• Example:

  int left = 0, right = arr.length - 1;
  while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) return mid;
      else if (arr[mid] < target) left = mid + 1;
      else right = mid - 1;
  }
  return -1;

• Related Questions:

  • Search in Rotated Sorted Array
  • Find Peak Element
  • First Bad Version

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Access (arr[index])	O(1)	O(1)
Update (arr[index] = x)	O(1)	O(1)
Length (arr.length)	O(1)	O(1)
Iteration	O(n)	O(1)
Sorting (Arrays.sort())	O(n log n)	O(log n)
Linear Search	O(n)	O(1)
Binary Search	O(log n)	O(1)
Copy (Arrays.copyOf())	O(n)	O(n)
Fill (Arrays.fill())	O(n)	O(1)

Related Leetcode Questions

Easy

1. Two Sum
2. Remove Duplicates from Sorted Array
3. Best Time to Buy and Sell Stock

Medium

1. Container With Most Water
2. Subarray Sum Equals K
3. Search in Rotated Sorted Array

Hard

1. Trapping Rain Water
2. Sliding Window Maximum
3. Median of Two Sorted Arrays