Algorithmic thinking: The Two-Sum problem.

Computational thinking, also known as algorithmic thinking, is the process of breaking down a complex problem into smaller, more manageable steps that can be solved using a computer or machine. It is a systematic approach to problem-solving that helps people develop logical and critical thinking skills.

Algorithmic thinking was originally developed by computer scientists, but it is now recognized as a way of solving problems that anyone can use in their personal or professional life. The goal is not to imitate the way computers think, but to adopt the problem-solving techniques that computer scientists often use.It can be applied to a wide range of fields, including artificial intelligence and mathematics, to solve problems.

The programming language Python is often used in this process to express solutions on a computer, particularly in statistical analysis.

Algorithmic thinking typically involves four key elements:

1. Decomposition: Dividing a complex problem into smaller, more manageable parts.

2. Pattern recognition: Identifying similarities within the problem.

3. Abstraction: Focusing on the most important information and ignoring less relevant details.

4. Algorithms: Developing a clear, step-by-step plan or set of rules to solve the problem.

Computational/Algorithmic thinking is often used to solve problems that have a clear structure, such as those that require an algorithm to solve them.

The Two-Sum problem - A classic in coding interviews

...and a perfect example to learn what algo thinking is like.

The Two-Sum problem is a common problem in computer science and algorithms, and it is not attributed to any specific person or group. It is a simple problem that has likely been independently discovered by many different individuals over time. It is commonly used as a benchmark problem to test the efficiency of different algorithms and is found in many different areas of computer science and mathematics. It has also been used in coding interviews and competitions.

The Two-Sum has been known to appear in Facebook and Google interviews.

The problem: Given a random list of numbers, we have to find a pair which add up to a given value. And we have to identify the indices of the values which sum to this number. The indices must be distinct and you can't use the same value in the same position twice.

How does that look like?

For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

We need to understand the concepts of space and time complexity to get around this problem. From Geeks For Geeks:

Time complexity:

Q. Imagine a classroom of 100 students in which you gave your pen to one person. You have to find that pen without knowing to whom you gave it.

Here are some ways to find the pen and what the O order is.

• O(n2): You go and ask the first person in the class if he has the pen. Also, you ask this person about the other 99 people in the classroom if they have that pen and so on, This is what we call O(n2).

• O(n): Going and asking each student individually is O(N).

• O(log n): Now I divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).

I might need to do:

• The O(n2) searches if only one student knows on which student the pen is hidden.

• The O(n) if one student had the pen and only they knew it.

• The O(log n) search if all the students knew, but would only tell me if I guessed the right side.

Space Complexity:

• Auxiliary Space is the extra space or temporary space used by an algorithm.

• The space Complexity of an algorithm is the total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criterion than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort, and Heap Sort use O(1) auxiliary space. The space complexity of all these sorting algorithms is O(n) though.

Space complexity is a parallel concept to time complexity. If we need to create an array of size n, this will require O(n) space. If we create a two-dimensional array of size n*n, this will require O(n2) space.

In recursive calls stack space also counts.

So... How do you solve the problem on Python? (With the help of ChatGPT )

There are a few different ways to solve the two-sum problem in Python. Here are a few examples:

1. Brute Force Method:

   • You can use a nested loop to iterate through every pair of numbers in the array, and check if their sum is equal to the target value.

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

Here's how it works:

1. The function takes two inputs: a list nums of integers and a target value target.

2. It uses a nested loop to iterate through every pair of numbers in the input list.
   

   • The outer loop uses the range() function to iterate through the indices of the input list, starting from 0 up to the length of the input list.

   • The inner loop also uses the range() function, starting from i+1 up to the length of the input list.

• Inside the nested loop, the code checks if the sum of the current pair of elements (nums[i] and nums[j]) is equal to the target value.
  

  • If it is, then the function returns a list containing the indices of the two elements that add up to the target value which is [i, j]

• 
  

• After the nested loop, the function returns None if no pair of elements that add up to the target value is found in the input list.

The time complexity of this method is O(n^2) because for every element in the input list, it has to go through the entire list again and check every pair of elements. This is why this is called a Brute force method, which is less efficient when compared to hash table based method. And the Space Complexity is O(1), as we are not using any extra memory here.

This method is simple and easy to understand, but it's not very efficient in terms of time complexity, especially when the input list is large. It's useful when you have a small input list or have only a few queries.

1. Using a Hash Table

   • A more efficient solution is to use a hash table to store the array elements. While iterating through the array, you check if the target value minus the current element is present in the hash table.

   • If it is, then you've found a pair of elements that add up to the target value.

def two_sum(nums, target):
    num_dict = {}
    for i, num in enumerate(nums):
        if target - num in num_dict:
            return [num_dict[target-num], i]
        num_dict[num] = i
    return None
        

Here's how it works:

1. The function takes two inputs: a list nums of integers and a target value target.

2. It first initializes an empty dictionary num_dict that will be used to store the elements of the input list as keys, and their indices as values.

3. It then iterates through the input list using a for loop, with the enumerate() function which returns a tuple containing the index and value of each element in the list.

4. Inside the loop, the code checks if the target value minus the current element (target - num) is present in the hash table.
   

   • If it is present, then this means that a pair of elements that add up to the target value is found.

   • Then the function returns a list containing the indices of the two elements that add up to the target value which is the value of num_dict[target-num] and i

• If the target value minus the current element is not found in the hash table, then it adds the current element as a key and its index as the value to the hash table.

• After the loop, the function returns None if no pair of elements that add up to the target value is found in the input list.

The time complexity of this method is O(n), because it goes through the input list once and performs a constant amount of work at each step. The space complexity of this method is O(n) as it uses a dictionary to store the elements of array. The main advantage of this method over the brute-force method is its improved time complexity and memory usage, by using hash table. It's also efficient when we have multiple queries and same array and we don't want to iterate through array again and again.

1. Sorting

   • Sort the given array, and use two pointers to iterate through the array, one starting from the beginning of the array, and the other one starting from the end.

   • if sum of elements at the two pointer is greater than the target, move the right pointer one step to left (towards the start of array)

   • if the sum of elements at the two pointer is less than the target, move the left pointer one step to the right.

def two_sum(nums, target):
    nums = sorted(nums)
    l, r = 0, len(nums)-1while l<r:
        if nums[l]+nums[r] == target:
            return [l, r]
        elif nums[l]+nums[r] < target:
            l +=1else:
            r -=1return None

1. The function takes two inputs: a list nums of integers and a target value target.

2. It first sorts the input list using the built-in sorted() function.

3. It then initializes two pointers l and r which will be used to iterate through the sorted input list:
   

   • l starts at the beginning of the sorted list and r starts at the end of the sorted list

• Inside the while loop, the code checks if the sum of the elements at the positions of the l and r pointer is equal to the target value.

  • If it is, then the function returns a list containing the indices of the two elements that add up to the target value which is [l, r]

• If the sum of elements at the two pointer is greater than the target, move the right pointer one step to left (towards the start of array)

  • And if the sum of elements at the two pointer is less than the target, move the left pointer one step to the right.

• After the while loop, the function returns None if no pair of elements that add up to the target value is found in the input list.

The time complexity of this method is O(n log n) because it needs to sort the array first which is O(n log n) and then iterates through the sorted array in linear time, O(n). And the Space Complexity is O(n) as it needs to keep a copy of the original array to return the indices. This method is a bit more complex than the previous two, but it also has the potential to be faster, especially when the input list is already sorted or nearly sorted. This is because it leverages the sorting algorithm and uses two pointers to scan through the array which reduces the time complexity.

All of the above methods have time complexity of O(n), but their space complexity is different. The first method has a O(1) space complexity as it doesn't use any extra memory. The second method has a O(n) space complexity as it use a hash table to store the elements of array. The third method has a O(n log n) space complexity as it uses sorting algorithm.

Each method has its own pros and cons, and the choice of which one to use will depend on the specific requirements of your problem.

We can only see a short distance ahead, but we can see plenty there that needs to be done. -Alan Turing