CoreJava – Arrays – Assignment - 2

 

 

Arrays Assignment - 2

1. Reverse Array:
• Description: Write a Java program to reverse an array of integers.
• Algorithm:
1. Start with two pointers, start pointing to the first element and end pointing to the last element of the array.
2. Swap the elements at the start and end pointers.
3. Move the start pointer to the right and the end pointer to the left.
4. Repeat steps 2-3 until the start pointer surpasses the end pointer.
2. Find Maximum Subarray:
• Description: Given an array of integers, find the contiguous subarray with the largest sum.
• Algorithm (Kadane's Algorithm):
1. Initialize two variables, maxSoFar and maxEndingHere, both set to the first element of the array.
2. Iterate through the array from the second element:
• Set maxEndingHere to the maximum of the current element or the sum of the current element and maxEndingHere.
• Set maxSoFar to the maximum of maxSoFar and maxEndingHere.
3. Return maxSoFar as the result.
3. Find Missing Number:
• Description: Given an array of integers from 1 to n with one number missing, find the missing number.
• Algorithm:
1. Calculate the expected sum using the Gauss formula: sum = (n * (n + 1)) / 2.
2. Iterate through the array and calculate the actual sum.
3. The missing number is the difference between the expected sum and the actual sum.
4. Rotate Array:
• Description: Given an array, rotate the elements to the right by a given number of steps.
• Algorithm:
1. Store the last element in a temporary variable.
2. Shift all elements to the right starting from the second-to-last element.
3. Place the temporary variable at the beginning of the array.
5. Find Duplicates:
• Description: Given an array of integers, find all the duplicate elements.
• Algorithm:
1. Sort the array to bring duplicate elements together.
2. Iterate through the sorted array and check for adjacent duplicate elements.
6. Merge Sorted Arrays:
• Description: Given two sorted arrays, merge them into a single sorted array.
• Algorithm:
1. Create a new array with a size equal to the sum of the sizes of the two input arrays.
2. Use two pointers, one for each input array, to compare elements and place them in the new array in sorted order.
3. Continue this process until all elements from both arrays are merged into the new array.
7. Find Peak Element:
• Description: Given an array of integers, find a peak element, which is greater than its neighbors.
• Algorithm:
1. Use binary search to find a peak element by comparing the middle element with its neighbors.
2. If the middle element is smaller than its adjacent elements, search in the direction of the larger adjacent element.
3. Repeat the process until a peak element is found.
8. Find Kth Largest Element:
• Description: Given an array of integers, find the kth largest element.
• Algorithm (Quickselect):
1. Choose a pivot element from the array.
2. Partition the array into two subarrays: elements smaller than the pivot and elements greater than the pivot.
3. If the pivot index is equal to k, return the pivot element.
4. If the pivot index is greater than k, recursively search in the left subarray.
5. If the pivot index is less than k, recursively search in the right subarray.
9. Move Zeroes to the End:
• Description: Given an array of integers, move all the zeroes to the end while maintaining the order of other elements.
• Algorithm:
1. Use two pointers, i and j, initialized to 0.
2. Iterate through the array with the i pointer.
3. If the element at i is non-zero, swap it with the element at j and increment j.
4. After iterating through the array, all non-zero elements will be at the beginning, and j will be the index of the first zero.
5. Set all elements from index j to the end of the array as zero.
10. Find Longest Consecutive Sequence:
• Description: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
• Algorithm:
1. Create a hash set and add all elements from the array to it.
2. Iterate through the array and for each element, check if it is the starting point of a sequence.
3. If an element is the starting point, keep counting the consecutive elements by incrementing a counter variable until the sequence ends.
4. Update the maximum length of the sequence encountered so far.
5. Return the maximum length of the consecutive sequence.
11. Find Intersection of Two Arrays:
• Description: Given two arrays, find their intersection (common elements).
• Algorithm:
1. Create two hash sets, one for each array, and store all elements from each array in their respective sets.
2. Iterate through one of the sets and check if each element is present in the other set.
3. If an element is common to both sets, add it to the result set.
4. Return the result set containing the intersection elements.
12. Find Median of Two Sorted Arrays:
• Description: Given two sorted arrays, find the median element.
• Algorithm:
1. Merge the two sorted arrays into a new sorted array.
2. Calculate the length of the merged array.
3. If the length is odd, return the middle element.
4. If the length is even, return the average of the two middle elements.
13. Find Subarray with Given Sum:
• Description: Given an array of integers and a target sum, find a subarray that sums up to the target sum.
• Algorithm:
1. Use two pointers, start and end, initially pointing to the first element.
2. Initialize a variable currentSum to the value of the first element.
3. Iterate through the array:
• If currentSum is equal to the target sum, return the subarray from start to end.
• If currentSum is less than the target sum, increment end and add the element at end to currentSum.
• If currentSum is greater than the target sum, subtract the element at start from currentSum and increment start.
4. If the target sum is not found, return null or an empty array.
14. Sort Colors (Dutch National Flag Problem):
• Description: Given an array containing only 0s, 1s, and 2s, sort the array in-place.
• Algorithm (Dutch National Flag Algorithm):
1. Use three pointers, low, mid, and high, initially pointing to the first element of the array.
2. Iterate through the array:
• If the element at mid is 0, swap it with the element at low and increment both low and mid.
• If the element at mid is 1, move to the next element by incrementing mid.
• If the element at mid is 2, swap it with the element at high and decrement high.
• Repeat these steps until mid surpasses high.
15. Next Permutation:
• Description: Given an array of integers, find the next lexicographically greater permutation.
• Algorithm:
1. Starting from the right, find the first pair of adjacent elements where the left element is smaller than the right element.
2. If such a pair is found, it means there is a possible permutation.
3. Find the smallest element to the right of the left element that is larger than the left element.
4. Swap the left and right elements.
5. Reverse the subarray to the right of the original left element.
6. If no such pair is found in step 1, it means the array is in descending order. In this case, reverse the entire array to get the next permutation.
16. Search in Rotated Sorted Array:
• Description: Given a rotated sorted array and a target element, find the index of the target element (if it exists).
• Algorithm:
1. Use binary search to find the pivot point, which is the element where the array is rotated.
2. Determine which part of the array (left or right of the pivot) the target element lies in.
3. Perform a regular binary search on the appropriate side of the pivot to find the target element.
17. Find Duplicate Number:
• Description: Given an array of integers containing n+1 elements where each integer is between 1 and n (inclusive), find the duplicate number.
• Algorithm (Floyd's Tortoise and Hare Algorithm):
1. Initialize two pointers, slow and fast, pointing to the first element of the array.
2. Move slow one step at a time and fast two steps at a time until they meet.
3. Once they meet, reset the slow pointer to the first element and keep the fast pointer where it is.
4. Move both pointers one step at a time until they meet again.
5. The meeting point is the duplicate number.
18. Sort Array by Parity:
• Description: Given an array of integers, sort the array such that all even elements come before odd elements.
• Algorithm:
1. Use two pointers, left and right, initially pointing to the first and last elements of the array.
2. Move the left pointer to the right until it encounters an odd element.
3. Move the right pointer to the left until it encounters an even element.
4. Swap the elements at the left and right pointers.
5. Repeat steps 2-4 until the left pointer surpasses the right pointer.
19. Find All Anagrams in a String:
• Description: Given a string and a pattern, find all the starting indices of the anagrams of the pattern in the string.
• Algorithm:
1. Create two hash arrays to store the character counts for the pattern and the current window of the string.
2. Initialize two pointers, start and end, pointing to the first element of the string.
3. Iterate through the string with the end pointer:
• Decrement the count of the character at end in the window hash array.
• If the window size exceeds the pattern size, increment the count of the character at start and move the start pointer to the right.
• If the window hash array matches the pattern hash array, add the start pointer to the result.
4. Return the list of starting indices of the anagrams.
20. Valid Sudoku:
• Description: Determine if a 9x9 Sudoku board is valid.
• Algorithm:
1. Create hash sets for each row, column, and 3x3 subgrid.
2. Iterate through each cell in the Sudoku board.
3. Check if the current cell value is already present in the corresponding row, column, or subgrid hash set.
4. If it is present, the Sudoku board is not valid.
5. If it is not present, add the value to the corresponding hash sets.
6. Repeat steps 2-5 for all cells in the Sudoku board.
7. If all cells pass the checks, the Sudoku board is valid.
21. Spiral Matrix:
• Description: Given a matrix of m x n elements, return all elements in spiral order.
• Algorithm:
1. Initialize four variables: top, bottom, left, and right, representing the boundaries of the matrix.
2. Initialize a result array.
3. Iterate in a spiral order:
• Traverse from left to right along the top row and add each element to the result array.
• Increment top to exclude the top row.
• Traverse from top to bottom along the right column and add each element to the result array.
• Decrement right to exclude the rightmost column.
• Traverse from right to left along the bottom row and add each element to the result array.
• Decrement bottom to exclude the bottom row.
• Traverse from bottom to top along the left column and add each element to the result array.
• Increment left to exclude the leftmost column.
4. Repeat steps 3 until all elements are added to the result array.
5. Return the result array.
22. Jump Game:
• Description: Given an array of non-negative integers, determine if you can reach the last index starting from the first index.
• Algorithm:
1. Initialize a variable maxReach to the first element of the array.
2. Iterate through the array:
• If maxReach is less than the current index, it means we cannot reach the current index. Return false.
• Update maxReach to the maximum of maxReach and the sum of the current index and its value.
• If maxReach is greater than or equal to the last index, return true.
3. If the loop completes, it means we can reach the last index. Return true.
23. Two Sum:
• Description: Given an array of integers and a target value, find two numbers that sum up to the target.
• Algorithm:
1. Create a hash map to store the complement of each element and its index.
2. Iterate through the array:
• Check if the complement of the current element exists in the hash map. If it does, return the indices of the two numbers.
• If the complement does not exist, add the current element and its index to the hash map.
3. If no solution is found, return an empty array or null.
24. Maximum Subarray Product:
• Description: Given an array of integers, find the contiguous subarray with the maximum product.
• Algorithm:
1. Initialize two variables, maxSoFar and minSoFar, both set to the first element of the array.
2. Initialize a variable maxProduct to maxSoFar.
3. Iterate through the array from the second element:
• Update maxSoFar and minSoFar by comparing the current element with the product of the current element and maxSoFar or minSoFar.
• Update maxProduct to the maximum of maxProduct and maxSoFar.
4. Return maxProduct as the result.
25. Valid Mountain Array:
• Description: Given an array of integers, determine if it is a valid mountain array.
• Algorithm:
1. Check if the array length is at least 3. If not, return false.
2. Iterate through the array until the elements are strictly increasing.
3. If there are no increasing elements or the increasing elements are at the beginning or end of the array, return false.
4. Continue iterating until the elements are strictly decreasing.
5. If there are no decreasing elements or the decreasing elements reach the end of the array, return true.
6. If the loop completes without returning, the array is not a valid mountain array. Return false.