Best ways to Minimize Time Complexity and Space Complexity of an Algorithm In Java!

Analysis of algorithms is very crucial part. It is important to find most efficient algorithms for solving a problem. It is possible to have many algorithms to solve a problem, but the challenge is to choose the most efficient one.

Now the point is, how can we recognize the most efficient algorithm if we have a set of different algorithms? Here, the concept of space and time complexity of algorithms comes into existence. Space and time complexity acts as a measurement scale for algorithms. We compare the algorithms on the basis of their space (amount of memory) and time complexity (number of operations).

Here are the ways:

Also,we will discuss some of the top questions appeared in FAANG(FaceBook, Amazon, Apple, NetFlix, Google).

Two Pointer Method: As name suggests in this method we use two pointers in order to solve any complex iterative problem instead of using nested loops we can go for two pointers method .

Steps:

1. int a=0;
   int b=s.length-1;
   while(a<b)
   {
   char temp=s[a];
   s[a]=s[b];
   s[b]=temp;
   a=a+1;
   b=b-1;
   }
2. Here, you can see a simple problem to reverse string in this instead of using nested loops and making it more complex, I have used two pointers one Is at the beginning of the array and other is at the end of array and simply swapped the values. So the time complexity becomes O(n)(Linear Time) and since, we are not using any extra place here space complexity becomes O(1)(Constant Space /In place).

By Using HashSet: As we know HashSet class is used to create a collection that uses a hash table for storage HashSet stores the elements by using a mechanism called hashing. HashSet contains unique elements only HashSet allows null value.

Steps:

1. int sumOfSet = 0, sumOfNums = 0;
   Set<Integer> set = new HashSet();
2. for (int num : nums) {
   if (!set.contains(num)) {
   set.add(num);
   sumOfSet += num;
   }
   sumOfNums += num;
   }
   return 2 * sumOfSet -sumOfNums;
3. For the given example, we have to find a number which occurs only once in the array. So, for this approach instead of storing each element in another array and checking with every element whether we find any match a between them.The easiest way is to use HashSet.
4. So, the approach is if the number is already there in set then we are gonna add num with sumOfNums else, if the number is not there in HashSet. we will add it into HashSet and we will also add it with sumOfSet. Then at the end we will return te single non repeated number from the array.
5. Note: In return statement, we must follow the precedence rule else we won't get the answer right.
6. So for this approach since we know that, all arithmetic and logical operation take O(1) time and loop takes O(n) time and Hashset takes O(1) and also functions contains() and add() takes O(1) time so , Our overall time Complexity becomes O(n). And space complexity would be O(n) and since Hashset has space complexity of O(n).

Using HashMap: Java HashMap class implements the Map interface which allows us to store key and value pair, where keys should be unique.

Steps :

1. HashMap<Integer,Integer> map = new HashMap<>();
   for(int i=0;i<nums.length;i++)
   {
   int comp=target-nums[i];
   if(map.containsKey(comp))
   {
   return new int[]{map.get(comp), i};
   }
   map.put(nums[i],i);
   }
   throw new IllegalArgumentException(“no matc found”);
   }
2. In here the problem says that, you will be given a target and you have to return the sum of the two numbers which could result in target.
3. In this approach again we could have used the nested loops but, it could results in the O(n²) time which is quadratic time, so the best approach by using HashMap in this we are firstly, finding the difference between number and target and storing it into the variable called comp. And if the comp is present in the map te we return the index of the number and comp else we just put the value in the HashMap.
4. So the time complexity of the algorithm since we know that, loop takes O(n) time and HashMap Takes O(1) an also functions containsKey(),put(),get() as the O(1) so overall time complexity becomes O(n) similarly, for space complexity of HashMap is O(n).

Hope you Enjoy This!

Stay Healthy, Stay Safe!