Create logic that will sum each element from arrA against every element from ArrB and output the indexes of the two items when their sum gives zero

user_10627724 0
Viewed 40

I was asked a question in an interview and found not the most optimal solution. How can this code be improved?

Create C# logic that will sum each element from arrayA against every element from ArrayB and output the indexes of the two items when their sum gives zero.

int[] arrayA = new int[] { 5, 7, 9, 7, 13 };
int[] arrayB = new int[] { 5, -7, 10, 7, 34, -5 };

so the first sum will be 5+5 which is not zero so we dont output anything. then 5+(-7) which also is not zero.
At some point you will get to
5 + (-5) which will be zero and the indexes will be 0,5 which is shown below as the first line of the output
Your output should show:
0,5
1,1
3,1
Since those are the indexes where a sum will equal to zero. Focus on the easiest solution

public class Program
{
    public static void Main()
    {
        int[] arrayA = new int[] { 5, 7, 9, 7, 13 };
        int[] arrayB = new int[] { 5, -7, 10, 7, 34, -5 };

        for (int i = 0; i < arrayA.Length; i++)
        {
            for (int j = 0; j < arrayB.Length; j++)
            {
                var sum = arrayA[i] + arrayB[j];
                if (sum == 0)
                    Console.WriteLine($"arrayA[{i}] + arrayB[{j}] = 0");
            }
        }
    }
}

Current time complexity O(m*n).

Updated:

Thank you m.raynal! New time complexity O(m+n)
Here C# code:

    private static void SolutionFast(int[] arrayA, int[] arrayB)
    {
        var dictB = ArrayToDict(arrayB);

        var result = new List<KeyValuePair<int, int>>();
        for (var idxA = 0; idxA < arrayA.Length; idxA++)
        {
            var val = -arrayA[idxA];
            if (dictB.ContainsKey(val))
            {
                for (var idxB = 0; idxB < dictB[val].Count; idxB++)
                {
                    result.Add(new KeyValuePair<int, int>(idxA, dictB[val][idxB]));
                }
            }
        }

        foreach (var elem in result)
        {
            Console.WriteLine($"{elem.Key}, {elem.Value}");
        }
    }

    private static Dictionary<int, List<int>> ArrayToDict(int[] arr)
    {
        var dict = new Dictionary<int, List<int>>();

        for (var i = 0; i < arr.Length; i++)
        {
            if (!dict.ContainsKey(arr[i]))
            {
                dict.Add(arr[i], new List<int> { i });
            }
            else
            {
                dict[arr[i]].Add(i);
            }
        }

        return dict;
    }
arrays algorithm
1 Answers

If you use a dictionary, you can get this time down to O(m+n).

First, you need to create a dictionary whose keys are the elements of the array B, and the values are the set of indices at which we find these elements.
On the example of the question, we would have

dict = {
   5: {0}, 7: {1, 3}, 9: {2}, 13: {4}
}

You can then output easily the result couples (pseudocode):

result = empty list
for idx_a from 0 to length(arrayA) - 1 do {
    val = arrayA[idx_a]
    if val is a key of dict then {
        for idx_b in dict[val] do {
            result.add((idx_a, idx_b))
        }
    }
}
return result

This can run in O'm+n) thanks to the implementation of dictionaries and sets, which allow lookup in O(1).

user_74426730
Related