<story><title>Solving “Two Sum” in C with a tiny hash table</title><url>https://nullprogram.com/blog/2023/06/26/</url></story><parent_chain><item><author>nkurz</author><text>I think it&amp;#x27;s a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version.  You&amp;#x27;d have to keep an additional mapping from the sorted to original positions.   And are we counting the sorting and space for the maps as free?  Or do we have to account for them somehow?&lt;p&gt;Mostly, I just don&amp;#x27;t like the problem specification.  What does it actually mean to &amp;quot;solve it efficiently&amp;quot;?  How many times are we going to be searching each input array?  How much memory do we have available?  What tradeoff between memory and computation is allowable?  How much does a comparison cost us versus accessing memory?  Are all targets equally likely?&lt;p&gt;Assuming as theoretical computer scientists tend to do that we can ignore all constant time operations, that access to memory is free, that an unknown but fixed amount memory is available, and that we&amp;#x27;ll be searching the same array forever ruins the problem for me.  Fill in the numbers and we can talk about what&amp;#x27;s optimal, but the &amp;quot;spherical cow&amp;quot; approach does nothing for me.</text></item><item><author>tromp</author><text>Sorting provides a alternative solution: sort the array, and then traverse a linear path over pairs of indices from (0,n-1) to (n-1,0) whose sum straddles the target:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    int main() {
      &amp;#x2F;* read in and sort array a *&amp;#x2F;

      int i=0,j=N-1, sum;

      while ((sum = a[i] + a[j]) != tgt) {
        if (sum &amp;lt; tgt)
          i++;
        else
          j--;
      }

      printf(&amp;quot;%d %d\n&amp;quot;, i, j);
    }&lt;/code&gt;&lt;/pre&gt;</text></item></parent_chain><comment><author>tialaramex</author><text>For the specifics, as someone else observed, walking nums to find the values we&amp;#x27;ve discovered and identify their indices is very affordable, it&amp;#x27;s N operations, and if we can&amp;#x27;t afford N we&amp;#x27;re in trouble since we definitely need to do at least N comparisons.&lt;p&gt;To your general point, sure, one thing that&amp;#x27;s nice (but takes a colossal effort) about Advent of Code is that it has specific inputs for players, and they have specific answers, so although it&amp;#x27;s usual for participants to write code which could (you hope) solve the problem in the abstract, the actual test is whether you solved the input you actually had. Sometimes not all conceivable inputs are even tractable (and some people find this situation frustrating if it happens) only the inputs given to real players may be suitable.&lt;p&gt;For this exercise the provided Go solution gets to handwave a bunch of problems. For example, Go&amp;#x27;s &amp;quot;map&amp;quot; hash table allocates whenever it wants to and has amortized table growth on top. That can really add up for a problem like this.&lt;p&gt;If I attacked it in Rust I would make HashMap::with_capacity(nums.len()) which does a single allocation up front, I might not &lt;i&gt;need&lt;/i&gt; all this space if I exit early, but it won&amp;#x27;t hurt. I don&amp;#x27;t know if there&amp;#x27;s even a way to write that in Go.</text></comment>
<story><title>Solving “Two Sum” in C with a tiny hash table</title><url>https://nullprogram.com/blog/2023/06/26/</url></story><parent_chain><item><author>nkurz</author><text>I think it&amp;#x27;s a little trickier than that, since the problem asks for the indices not the numbers, which would be lost in the sorted version.  You&amp;#x27;d have to keep an additional mapping from the sorted to original positions.   And are we counting the sorting and space for the maps as free?  Or do we have to account for them somehow?&lt;p&gt;Mostly, I just don&amp;#x27;t like the problem specification.  What does it actually mean to &amp;quot;solve it efficiently&amp;quot;?  How many times are we going to be searching each input array?  How much memory do we have available?  What tradeoff between memory and computation is allowable?  How much does a comparison cost us versus accessing memory?  Are all targets equally likely?&lt;p&gt;Assuming as theoretical computer scientists tend to do that we can ignore all constant time operations, that access to memory is free, that an unknown but fixed amount memory is available, and that we&amp;#x27;ll be searching the same array forever ruins the problem for me.  Fill in the numbers and we can talk about what&amp;#x27;s optimal, but the &amp;quot;spherical cow&amp;quot; approach does nothing for me.</text></item><item><author>tromp</author><text>Sorting provides a alternative solution: sort the array, and then traverse a linear path over pairs of indices from (0,n-1) to (n-1,0) whose sum straddles the target:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    int main() {
      &amp;#x2F;* read in and sort array a *&amp;#x2F;

      int i=0,j=N-1, sum;

      while ((sum = a[i] + a[j]) != tgt) {
        if (sum &amp;lt; tgt)
          i++;
        else
          j--;
      }

      printf(&amp;quot;%d %d\n&amp;quot;, i, j);
    }&lt;/code&gt;&lt;/pre&gt;</text></item></parent_chain><comment><author>marginalia_nu</author><text>For an input array of values I[],  create an array A = [ 0 ... n ] so that n = len(I). Sort the indices in A based on their corresponding value in I. Now A &lt;i&gt;is&lt;/i&gt; the mapping, A[n] is the index in I of the n+1:th largest value, and you can binary search in the same way, by comparing I[A[i]].&lt;p&gt;This is strictly more space efficient than a hash table. You&amp;#x27;re not going to win any awards for being cache efficient, but then again, when the competition is a damn hash table it&amp;#x27;s not too bad ;P</text></comment>