Two Sum (BruteForce)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Acceptance Criteria:

• You may assume that each input would have exactly one solution
• You may not use the same element twice
• You can return the answer in any order.

Example 1:

Inputs: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[4] = 6, we return [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Intuition

Let's take an example and implement our very basic brute-force solution.
input = [11,2,15,7] and target = 9
expected output = [1, 3]

Cycle 1

Let's start the cycle-1, where i starts from index 0 and j from next index of i

At the end of the cycle 1, we haven't find our desired numbers which add up to the targeted sum

Cycle 2

Now again, start the cycle-2, where i starts from index 1 and j starts from index 2 (next index of i)

Why is j always starting from right next to i
To ensuring, we only check numbers that appear after nums[i] to avoid redundant checks and prevents using the same element twice.

So we can think of the loop like this

class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		for i in range(len(nums)):
			for j in range(i+1, len(nums)):
				# do checking and stuffs

• The outer loop (i) iterates through each element in the nums list, treating it as the first number in the potential pair.
• The inner loop (j) starts from i + 1, ensuring that we only check numbers that appear after nums[i]. This avoids redundant checks and prevents using the same element twice.
  For an instance: num[0], num[1] is already checked in cycle-1. There is no need to revisit the same pair of indices again.

Let's visualize the second cycle now,

Cool, we just have found our desired pair of numbers 2, 7 which add up to the target sum 9
So, we will return a list indices [1, 3]

Complete Code Snippet

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

Complexity Analysis

Time Complexity

This nested loop structure systematically examines all possible pairs in nums, making it a brute-force approach with a time complexity of O(n²).

Space Complexity

We haven't used any additional data-structure, so the space complexity is O(1)

Improvement Note

Though this approach is simple and easy to implement, it becomes inefficient when the size of nums is really large.

Can we do better? Can we solve it in Linear time complexity O(n)?
That is also ok, If the space complexity grows to O(n).
Check out the optimized Two Sum solution.

Thanks for Stopping by! Happy Leet coding

Connect with me on