Problem solving using Swift: Part 2

Photo by Olav Ahrens Røtne on Unsplash

Continuing Part 1, We are going to solve more problems today. As promised to come up with new problem statements and their solutions daily, You can follow me for fresh articles.

Problem Statement 3 : We are given an unsorted array of non-negative integers, find a continuous subarray which adds to a given number.

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4
Explanation: Sum of elements between indices
1 and 4 is 4 + 0 + 0 + 3 = 7

Solution 1 : Simple approach is to iterate given array using 2 loops. Complexity of this approach is O(n²), it doesn’t seems an optimal approach but lets start with simple one 👇

Solution 2 : Lets optimise above approach to improve time complexity from O(n²) to O(n). As all the item in given array are positive, we can make use of two pointer start & last to assess if we are on the right track.

Problem Statement 4 : We are given an unsorted array of integers (could be negative also), find a continuous subarray which adds to a given number. If there are more than one subarray with the required sum, print start and end index for any of them.

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Output: Sum found between indexes 0 to 3
Explantion: Sum of elements between indices
0 and 3 is 10 + 2 - 2 - 20 = -10

Solution 1 : Simple approach by using two for loops with time complexity O(n²) 👇

Solution 2 : We have to optimise above approach, challenging part here is that we can also have negative number in array🤔.

One solution can be like if we create a dictionary “prefixDict” to hold sum of elements upto that index. To check if there is a subarray with sum equal to “sum”, check for every index “i”, If there is an entry in “prefixDict” with sum equal to currentSum - sum, then the subarray with given sum is found. The time complexity of this approach is O(n) but we are using extra space with space complexity O(n). 👇

Problem Statement 5: Interviewer makes a tweak in above question and ask you to solve it without using any extra space. 🤔🙃

Solution: To solve it in space, First find smallest negative number in array, if exist and then increment every value in the array by the absolute value of the smallest negative element found. Now whole array get converted into a positive integer array. By doing this transformation sum of every sub array also increases by number of elements in the sub array * absolute value of smallest negative element found. Now problem reduces to find if there is any subarray in the given array of only positive numbers with the new target sum. This can be done using same technique in O(n) time and constant space as in Problem Statement 3 : Solution 2. 😀

To continue move to Part 3.

Thanks for reading this🙏🙏. Any feedback in the comments would be appreciated. If you enjoyed reading this post, please share and give some claps👏👏. I will come with 2 new problems and their optimised solution every day.

You can follow me for fresh articles.