Set 2 - Arrays
Integer
Sum of Array Elements
Method 1: Using iteration
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 2: Using Streams
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3: Using Recursion
Time Complexity: O(n)
Auxiliary Space: O(n)
Largest element in an array
Method 1: Using iteration
Time Complexity: O(n), where n represents the size of the given array. Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method 2: Using streams
Time Complexity: O(n), where n represents the size of the given array. Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method 3: Using manual sorting
Sorting the array using Insertion Sort and returning last element from the sorted array
Time Complexity: O(n logn), where n represents the size of the given array. Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method 4: Using sorting via Arrays.sort(..)
Time Complexity: O(n logn), where n represents the size of the given array. Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method 5: Using Collections.max()
Array Rotation
Method 1: Using additional array
Time complexity: O(N) Auxiliary Space: O(N)
Method 2: Using rotation one by one
Time Complexity: O(N * d) Auxiliary Space: O(1)
Method 3: Using Juggling algorithm for array rotation
Refer to this page -> https://pranaypourkar.gitbook.io/java-knowledge-base/java/algorithm/set-1#juggling-algorithm-for-array-rotation
Remove duplicate elements from an Array
Input: arr[] = {2, 1, 2, 2, 3, 4, 4, 4, 5, 5} Output: arr[] = {1, 2, 3, 4, 5}
Method 1: Using Set
Time Complexity: O(n) (iterating through the array once) Auxiliary Space: O(n) (to store unique elements in the Set)
Method 2: Using ArrayList
Time Complexity: O(n^2) in the worst case (nested loop with contains() method) Auxiliary Space: O(n) (to store unique elements in the ArrayList)
Method 3: Using Sorting
Sort the array and use the approaches given below.
Remove duplicate elements from a SortedArray
Method 1: Using Iteration and Sorting
Time Complexity: O(N) Auxiliary Space: O(N)
Method 2: Maintaining a separate index for unique elements
Steps
Traverse input array from i = 0 to N:
Keep track of the count of unique elements. Let this count be j.
Swap arr[j] with arr[i].
At last, return j.
Time Complexity: O(N) Auxiliary Space: O(1)
Remove all occurrences of an element from Array
Method 1: Using iteration
Time Complexity: O(n) Space Complexity: O(n)
Method 2: Using Streams
Time Complexity: O(n)
The Arrays.stream(arr)
operation takes O(n) time, where n is the length of the input array arr
. The filter()
operation iterates through each element of the stream and applies the predicate num -> num != key
. In the worst case, this operation also takes O(n) time. The toArray()
operation collects the elements of the stream into an array, which takes O(n) time.
Space Complexity: O(n)
The space complexity is O(n) because we are creating a new array to store the filtered elements. The size of this array is equal to the number of elements that pass the filter condition, which could be up to n elements in the worst case.
Method 3: Using List
Time Complexity: O(n)
Creating the list arrList
from the array arr
using IntStream.of(arr).boxed().collect(Collectors.toList())
takes O(n) time, where n is the length of the input array arr
. Remaining is same as above Method.
Space Complexity: O(n)
String
Char
Last updated