Longest Harmonious Subsequence in Java
The Longest Harmonious Subsequence problem is a well-known algorithmic problem in computer science that involves finding the longest subsequence of a given array in which the difference between the maximum and minimum element is exactly one.
Example 1:
Input: {1,3,2,2,5,2,3,7}
Output: 5
Explanation: The longest harmonious subsequence in this array is {3, 2, 2, 2, 3}, which has a length of 5.
Example 2:
Input: {1,2,3,4,5}
Output: 2
Explanation: The longest harmonious subsequence in this array is {1, 2}, which has a length of 2.
Example 3:
Input: {1,1,1,1}
Output: 0
Explanation: There are no adjacent elements in this array that differ by 1, so there is no harmonious subsequence
Approach: Using Brute Force
The brute-force approach to solve the Longest Harmonious Subsequence problem involves checking every possible subsequence of the input array to find the longest one that meets the harmonic condition. It involves iterating through the array twice, with the outer loop iterating over each element of the array, and the inner loop iterating over each element of the array again to check each possible subsequence.
ALGORITHM:
Step 1: Initialize a variable maxLen to 0.
Step 2: Iterate through each element in the array.
Step 3: Initialize a variable count to 0 and a boolean variable found to false.
Step 4: Iterate through each element in the array again.
Step 5: If the current element is equal to the element at the outer loop index or one greater than it, increment count.
Step 6: If the current element is one greater than the element at the outer loop index, set found to true.
Step 7: If found is true, update maxLen to the maximum of its current value and count.
Step 8: Return maxLen.
FileName: LongestHarmoniousSubsequence.java
import java.util.Arrays;
public class LongestHarmoniousSubsequence {
public static int findLHS(int[] nums) {
// Initialize a variable maxLen to 0 to store the length of the longest harmonious subsequence
int maxLen = 0;
// Iterate through each element in the array
for (int i = 0; i < nums.length; i++) {
// Initialize a variable count to 0 to count the number of elements in the subsequence
// and a boolean variable found to false to check if there exists an element in the subsequence
// that is one greater than the current element
int count = 0;
boolean found = false;
// Iterate through each element in the array again to form a subsequence with the current element
for (int j = 0; j < nums.length; j++) {
// If the current element is equal to the element at the outer loop index or one greater than it,
// increment count as it is part of the subsequence
if (nums[j] == nums[i] || nums[j] == nums[i] + 1) {
count++;
}
// If the current element is one greater than the element at the outer loop index,
// set found to true as we have found an element that satisfies the condition for a harmonious subsequence
if (nums[j] == nums[i] + 1) {
found = true;
}
}
// If found is true, update maxLen to the maximum of its current value and count
if (found) {
maxLen = Math.max(maxLen, count);
}
}
// Return the length of the longest harmonious subsequence
return maxLen;
}
public static void main(String[] args) {
int[] nums1 = {1,3,2,2,5,2,3,7};
System.out.println("Input: nums1 = " + Arrays.toString(nums1));
System.out.println("Output: " + findLHS(nums1)); // Output: 5
int[] nums2 = {1,2,3,4};
System.out.println("Input: nums2 = " + Arrays.toString(nums2));
System.out.println("Output: " + findLHS(nums2)); // Output: 2
}
}
Output:
Input: nums = [1, 3, 2, 2, 5, 2, 3, 7]
Output: 5
Input: nums = [1, 2, 3, 4]
Output: 2
Complexity Analysis:
Time complexity: The time complexity of the findLHS
function is O(n^2), where n is the length of the input array nums
. Here we are iterating through the array twice with nested loops. The outer loop has n iterations and the inner loop also has n iterations in the worst case, resulting in O(n^2) time complexity.
Space Complexity: The space complexity of the function is O(1) because we are only using a constant amount of extra space to store the variables maxLen
, count
, and found
. These variables are not dependent on the size of the input array and do not increase in size as the input size increases. Therefore, the space complexity is constant, or O(1).
Approach: Using HashMap
The solution to the Longest Harmonious Subsequence problem involves the use of a hash map. A hash map is a data structure that allows us to store key-value pairs, where each key is unique and maps to a corresponding value.
ALGORITHM:
Step 1: Create a HashMap to store the frequency of each element in the given array.
Step 2: Traverse through the array and update the frequency of each element in the HashMap.
Step 3: Traverse through the array again and for each element, check if the HashMap contains the adjacent element (i.e., the element whose difference is one).
Step 4: If the adjacent element is present in the HashMap, then calculate the length of the subsequence that includes both elements and update the maximum length found so far.
Step 5: Return the maximum length as the result.
FileName: LongestHarmoniousSubsequence
import java.util.HashMap;
public class LongestHarmoniousSubsequence {
public static void main(String[] args) {
int[] nums = {1, 3, 2, 2, 5, 2, 3, 7};
int[] nums1 = {1, 2, 3, 4, 5};
int[] nums2 = {1, 1, 1, 1};
// Find the longest harmonious subsequence length for each array and print the result
int result = findLHS(nums);
System.out.println("Longest harmonious subsequence length: " + result); // Output: Longest harmonious subsequence length: 5
int longestHS = findLHS(nums1);
System.out.println("Longest harmonious subsequence length: " + longestHS); // Output: Longest harmonious subsequence length: 2
int ans = findLHS(nums2);
System.out.println("Longest harmonious subsequence length: " + ans); // Output: Longest harmonious subsequence length: 0
}
public static int findLHS(int[] nums) {
// Create a HashMap to store the frequency of each element
HashMap<Integer, Integer> freqMap = new HashMap<>();
int maxLen = 0;
// Update frequency of each element in the HashMap
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Traverse through the array and check for adjacent elements
for (int num : nums) {
if (freqMap.containsKey(num + 1)) { // Check if the adjacent element is present
// Calculate the length of the subsequence that includes both elements
int len = freqMap.get(num) + freqMap.get(num + 1);
// Update the maximum length found so far
maxLen = Math.max(maxLen, len);
}
}
// Return the maximum length found
return maxLen;
}
}
Output:
Longest harmonious subsequence length: 5
Longest harmonious subsequence length: 2
Longest harmonious subsequence length: 0
Complexity Analysis:
Time complexity: O(n), where n is the length of the input array. We traverse through the array twice, once to update the frequency map and once to check for adjacent elements. The HashMap operations take O(1) time, so the overall time complexity is O(n).
Space complexity: O(n), where n is the length of the input array. The frequency map can store up to n entries, so the space complexity is O(n).
Approach: Using Sorting
ALGORITHM:
Step 1: Sort the input array.
Step 2: Initialize variables prevNum and prevFreq to the first element of the array and its frequency.
Step 3: Initialize a variable maxLen to 0
Step 4: Iterate through the sorted array starting from the second element.
Step 5: If the current element is equal to the previous element, increment prevFreq.
Step 6: Otherwise, if the current element is one greater than the previous element, update maxLen to the maximum of its current value and the sum of the frequencies of the current element and the previous element.
Step 7: Otherwise, update prevNum and prevFreq to the current element and its frequency.
Step 8: Return maxLen.
FileName: LongestHarmoniousSubsequence.java
import java.util.Arrays;
public class LongestHarmoniousSubsequence {
public static int findLHS(int[] nums) {
// Sort the input array.
Arrays.sort(nums);
// Initialize variables to track the start and end indices of a subsequence and the maximum length of the subsequence.
int start = 0;
int end = 0;
int maxLen = 0;
// Iterate through the sorted array.
for (int i = 1; i < nums.length; i++) {
// If the current number is one greater than the previous number, update the end index of the subsequence.
if (nums[i] == nums[i-1] + 1) {
end = i;
}
// If the current number is equal to the previous number, do nothing.
else if (nums[i] == nums[i-1]) {
continue;
}
// Otherwise, update the start index of the subsequence and compute the length of the subsequence.
else {
start = i;
end = i;
}
int len = end - start + 1;
// Update the maximum length of the subsequence.
if (len > maxLen) {
maxLen = len;
}
}
// Return the maximum length of the subsequence.
return maxLen;
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 2, 2, 5, 2, 3, 7};
System.out.println("Input: nums = " + Arrays.toString(nums1));
System.out.println("Output: " + findLHS(nums1)); // Output: 5
}
}
Output:
Input: nums = [1, 3, 2, 2, 5, 2, 3, 7]
Output: 5
Complexity Analysis:
The time complexity of this implementation is O(n log n), as we sort the input array using a quicksort algorithm that has an average time complexity of O(n log n).
The space complexity of this implementation is O(1), as we only use a constant amount of extra space for variables. Therefore, this implementation is more efficient than the brute-force approach and uses less space than the optimization approach that uses a hash map.