Advance Data Structure Assignment 1
Vansh Agarwal
Section-19 (22SCSE1010944)
1. Find the Largest Element in a Given Array
Algorithm:
1. Initialize a variable max with the first element of the array.
2. Traverse through the array.
3. Update max if the current element is greater than max.
4. Return max.
Program:
public class ArrayProblems {
public static int findLargest(int[] arr) {
if (arr.length == 0) {
throw new IllegalArgumentException("Array is empty");
}
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
2. Reverse a Given Array
Algorithm:
1. Initialize two pointers: one at the start and one at the end of
the array.
2. Swap the elements at these pointers.
3. Move the start pointer forward and the end pointer backward.
4. Repeat until the pointers meet.
Program
public class ArrayProblems {
public static void reverseArray(int[] arr) {
int start = 0, end = arr.length - 1;
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
Time Complexity: O(n)
Space Complexity: O(1)
3. Find the Second Largest Element in a Given Array
Algorithm:
1. Initialize two variables, first and second, with very low values
(e.g., Integer.MIN_VALUE).
2. Traverse the array.
3. Update first and second based on comparisons with the current
element
Program
public class ArrayProblems {
public static int findSecondLargest(int[] arr) {
if (arr.length < 2) {
throw new IllegalArgumentException("Array must
contain at least two elements");
}
int first = Integer.MIN_VALUE, second =
Integer.MIN_VALUE;
for (int num : arr) {
if (num > first) {
second = first;
first = num;
} else if (num > second && num < first) {
second = num;
}
}
if (second == Integer.MIN_VALUE) {
throw new IllegalArgumentException("No second largest
element found");
}
return second;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
4. Check if a Given Array is Sorted
Algorithm:
1. Traverse through the array and check if each element is less
than or equal to the next one.
Program
public class ArrayProblems {
public static boolean isSorted(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
5. Remove Duplicates from a Given Array
Algorithm:
1. Use a HashSet to keep track of seen elements.
2. Traverse the array and add only unseen elements to a new list.
Program
import java.util.HashSet;
import java.util.ArrayList;
public class ArrayProblems {
public static int[] removeDuplicates(int[] arr) {
HashSet<Integer> seen = new HashSet<>();
ArrayList<Integer> result = new ArrayList<>();
for (int num : arr) {
if (!seen.contains(num)) {
seen.add(num);
result.add(num);
}
}
// Convert ArrayList to array
return result.stream().mapToInt(i -> i).toArray();
}
}
Time Complexity: O(n)
Space Complexity: O(n)
6.Rotate a Given Array
Algorithm:
1. Use array slicing to rotate the array. For example, to rotate right
by k positions.
Program:
public class ArrayProblems {
public static void rotateArray(int[] arr, int k) {
int n = arr.length;
k %= n; // In case k is greater than array length
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
}
private static void reverse(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
Time Complexity: O(n)
Space Complexity: O(1)
7. Find the Frequency of Elements in a Given Array
Algorithm:
1. Use a HashMap to count the occurrences of each element.
Program
import java.util.HashMap;
public class ArrayProblems {
public static HashMap<Integer, Integer>
elementFrequency(int[] arr) {
HashMap<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
return freqMap;
}
}
Time Complexity: O(n)
Space Complexity: O(n)
8. Merge Two Sorted Arrays
Algorithm:
1. Use two pointers to traverse both arrays and merge them into a
new array.
Program
public class ArrayProblems {
public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
int n1 = arr1.length;
int n2 = arr2.length;
int[] merged = new int[n1 + n2];
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
while (i < n1) {
merged[k++] = arr1[i++];
}
while (j < n2) {
merged[k++] = arr2[j++];
}
return merged;
}
}
Time Complexity: O(n + m) (where n and m are the lengths of the
two arrays)
Space Complexity: O(n + m)
