Change the Approach | Different Ways to Solve Same Problem

The way we approach a problem decides the effort its going to take to solve it. It may seem like an obvious thing but sometimes we engineers get stuck thinking in just one direction and we cannot look the other way.

I would try to explain this with an example today.

Let's take this simple leet code example, Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

First Approach

Probably, the first solution in your mind is to loop over the entries in a way so that you can compare every element with the next one to check if its same and then just return true there. Sounds reasonable and also doable, let's look at the code here:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:

        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True

        return False

The solution actually works and is not a problem for smaller arrays to do this but as you might have guessed this is a brute force solution and the time complexity for this solution is O(n^2) BigO of N-Square, because we will execute both loops n-1 times.

Second Approach

The second approach is completely different than the first one and it improves the algorithm greatly.
In this approach, instead of comparing every element with the rest of the elements, we will keep track of all the visited elements and whenever we encounter an element which we have visited/tracked already we know we have a duplicate entry in the array.
Some simple python code will solve it really easily.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        visitedHashMap = {}

        for num in nums:
            if num in visitedHashMap.keys():
                return True

            visitedHashMap[num] = num

        return False

This approach is far more efficient than the first one but it uses more memory which is O(n) as we will created a hash map for storing the visited elements.

Second Approach - Slight variation

Instead of checking if the num key exists in the hashMap we can simply try to get the key and we know if we don't have a key, python will throw a KeyError and we can pass this exception as we know there are keys which are checked for the first time.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        visitedHashMap = {}

        for num in nums:
            try:
                visitedHashMap[num]
                return True
            except KeyError:
                visitedHashMap[num] = num

        return False

Which approach is better, I leave that judgement to you guys but I explained the above scenarios in order to build some background for the actual problem I wanted to share with you guys.

The Actual Problem

There's a relatively famous problem where you are being asked to provide the count of all possible combinations from an array of integers which adds up to a given target.
The problem statement is:

Given an array nums of positive integers, provide count for all the possible combinations which adds up to a given target. The combinations should have at least two elements and should be in descending order.

Input: nums = [1,2,3,4], target=5
Output: 2

Explanation

For the given target 5, the possible combinations satisfying the above said conditions are:

[4,1]
[3,2]

If you are someone like me, you will also try to create all possible combinations which satisfy the above conditions for the given target and then just return the count of those combinations.

While this is also a valid approach and it can work, there's a slight problem.

Imagine if the target is 300 and the given nums array is [1,2,3,4,5,6,7,8,9,........199]
Can you imagine how many valid combinations you can have in this case? Let's just say A LOT!!!

I wrote a solution in python with some dynamic programming techniques but still I was unable to calculate the combinations for even bigger numbers.

After a bit of struggle I took a break - sat in my garden and reflected on my approach and realise I have to change my approach because if my current approach can only provide solution to some extent only, that can not be a valid solution.

Finally, long story short, after reading a bunch of mathematics forum I found out this problem is related to a domain of mathematics called partition and once I understood that it was really easy to write some python code which solve the problem in really minimum time.