Printing element combinations that make a neutral compound An array is given with the element name and their respective pH values. Print the combination of 2 elements which make a neutral compound


Here is the solution that I came up with but uses a Hashmap hence O(N) space complexity. Any idea I can reduce space complexity but maintaining O(N) time complexity

   public static void FindCombinationSuchThatPHValueIsNeutralized(PhValue[] input)
         {
             var map = new Dictionary&lt;int, string&gt;();
             foreach (var phValue in input)
             {
                 if (!map.ContainsKey(-phValue.Value))
                 {
                     map.Add(phValue.Value, phValue.Element);
                 }

                 else
                 {
                     Console.WriteLine(phValue.Element + "," + map[-phValue.Value]);
                     break;
                 }


             }

         }
I don't believe you can reduce the space complexity, and still maintain the \$O(n)\$ time complexity. There is a trade off here you have to compromise on. Of course, you can, if you want, run on \$O(1)\$ space complexity, but your time complexity will have to be compromised.

Now, your code has a bug.... it needs to add the element to the Dictionary even when it has a match for neutral.... Consider a data set like (fake elements and pH's):

H 0
He 1
C -1
Au 1
...


Then, I would expect there to be two matches, both C and He are 0, and Au and C are 0, but, when you matched C against He, you did not add C to the Dictionary, so it is not in the Dictionary when you process Au, and the match is missed.

Unfortunately, as you add the Au on the match, though, you will overwrite the existing He entry.... because you do not support multiple elements with the same pH.

You need your map to be a Dictionary&lt;Int, IList&lt;string&gt;&gt;, and you need to add the element to the list for the respective pH, Then, when you find a match, you need to map it against all the other Elements....

I believe this will require a full process once through the data, and then another to go through the keys of the Dictionary.

Edit: A third bug (thanks @Heslacher) is that the neutral pH is 7, so your check should be:

if (!map.ContainsKey( 7 - (phValue.Value - 7))