By Alex Rintt (Last update November 30, 2022)

November 30, 2022 • Edit this file (Private, ask me for access if you wanna contribute)

LeetCode, Two Sum problem solution using brute force in Dart

Two Sum LeetCode problem solution written in Dart in complexity O(N).

carbon (1)

Lets solve this problem from LeetCode: leetcode.com/problems/two-sum.

In the past I was addicted to algorithm exercises, in the old gold URI Online, what now is a preview of hell called Beecrowd, I need to write why I hate this website some time. But lets skip to what matters:

Given an array of N integers nums<int>, find the indices of two elements which the sum are equals to a given integer target.

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: 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]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

The O(n²) is pretty simple: for each element of the array try to find a integer that summed is equals to the target.

List<int> twoSum(List<int> nums, int target) {
  for (var i = 0; i < nums.length; i++) {
    // Get the current iteration element.
    final int current = nums[i];

    final j = nums.lastIndexOf(target - current);

    if (j != -1 && j != i) {
      return [i, j];
    }
  }

  // Never happens but due Dart null-safety you need to either throw an Exception or return the List<int>.
  return <int>[];
}

The catch part is:

nums.lastIndexOf(target - current);

This can be described as a simple find x statement where x is the second sum element:

e = current element; x = second sum element; target = the total sum we are searching for.

x = target - e

Since we are done calculating the "what element should I search for as second element?" now we need to add a if statement to skip when we do not find a second element and when the second element is the first element itself ("and you may not use the same element twice."):

// If j == -1 then we didn't find a corresponding element.
// If j == i then the second element is the first element itself.
if (j != -1 && j != i) {
  return [i, j];
}

Done, now we just return the i and j indices and submit our answer.

Challenge I wanna try next few days: find the optimized solution of this exercise; I'm not the dynamic programming guy yet, so I wanna Google and try to learn and understand, cheers me luck.

Anonymous message

The form above is anonymous, although the following data is collected:

Current page URL.
Your message.
Your username if provided.
Don't forget to include contact info if you are asking something, otherwise I'll never be able to reach you back!

If you prefer, you can reach me directly on GitHub or E-mail.

_{This form is powered by Discord Webhook API, so it is totally
hackable, enjoy.}

LeetCode, Two Sum problem solution using brute force in Dart

See also

Anonymous message