Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 1 - Brute Force

For each unique number in the array, count how many elements equal that number and how many equal that number plus one. If both counts are nonzero, the harmonious subsequence length is their sum. Track the maximum across all numbers.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0594.1 - Longest Harmonious Subsequence - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findLHS(self, nums: List[int]) -> int:
        """Longest Harmonious Subsequence Function"""
        result = 0
        for num in set(nums):
            count_num = nums.count(num)
            count_next = nums.count(num + 1)
            if count_next > 0:
                result = max(result, count_num + count_next)
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findLHS([1, 3, 2, 2, 5, 2, 3, 7]))  # 5
    print(Solution().findLHS([1, 2, 3, 4]))                # 2
    print(Solution().findLHS([1, 1, 1, 1]))                # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Hash Map (Counter)

Use a Counter to count the frequency of each number in a single pass. Then iterate through the counter and for each key, check if key + 1 also exists. If so, the harmonious subsequence length is the sum of both frequencies. Return the maximum.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0594.2 - Longest Harmonious Subsequence - Solution 2 - Hash Map (Counter) """

#####################################################################################
# Imports
#####################################################################################
from typing import List
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findLHS(self, nums: List[int]) -> int:
        """Longest Harmonious Subsequence Function"""
        count = Counter(nums)
        result = 0
        for num in count:
            if num + 1 in count:
                result = max(result, count[num] + count[num + 1])
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findLHS([1, 3, 2, 2, 5, 2, 3, 7]))  # 5
    print(Solution().findLHS([1, 2, 3, 4]))                # 2
    print(Solution().findLHS([1, 1, 1, 1]))                # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Sorting + Sliding Window

Sort the array first. Use two pointers to maintain a window where the difference between the max (right end) and min (left end) is at most 1. When the difference exceeds 1, advance the left pointer. Only update the result when the difference is exactly 1.

TimeComplexity: O(n \log n)

SpaceComplexity: O(1)

""" 0594.3 - Longest Harmonious Subsequence - Solution 3 - Sorting + Sliding Window """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findLHS(self, nums: List[int]) -> int:
        """Longest Harmonious Subsequence Function"""
        nums.sort()
        result = 0
        left = 0
        for right in range(len(nums)):
            while nums[right] - nums[left] > 1:
                left += 1
            if nums[right] - nums[left] == 1:
                result = max(result, right - left + 1)
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findLHS([1, 3, 2, 2, 5, 2, 3, 7]))  # 5
    print(Solution().findLHS([1, 2, 3, 4]))                # 2
    print(Solution().findLHS([1, 1, 1, 1]))                # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0594 - Longest Harmonious Subsequence

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Brute Force

Solution 2 - Hash Map (Counter)

Solution 3 - Sorting + Sliding Window

Solution 2 - Brute Force using `enumerate()`