Click here to Skip to main content
15,120,326 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Question:

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.
and
The code should be of time complexity less than O(n square)

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

The input for this is
nums[]=[50000000,3,2,4,50000000]
target=100000000

Error:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdad19f378 (pc 0x55791e218052 bp 0x7ffdb30fc410 sp 0x7ffdad19e380 T0)
#2 0x7f03492de0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
==30==ABORTING

Debugging:

I did debug for other inputs, this code worked fine. But here when I try to debug in this case (input) to find the mistake, The debugging was being stopped itself at the point of creating a hash table.
Is this because in this case, the hash table would be of length 100000000 ?
Is the error also because of that ?
As a hash table of huge length would be created , does that much space available in memmory ?
This code worked in remaining all test cases, but not worked in this one.


What I have tried:

C++
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i;
    int max=nums[0];
    int min=nums[0];
    for(i=0;i<numsSize;i++)
    {
        if(max<nums[i])
        {
            max=nums[i];
        }
        if(min>nums[i])
        {
            min=nums[i];
        }
    }
    int x,y;
    int max1=0;
    int min1=0;
    int largest=max;
    int smallest=min;
    if(max<0)
    {
        max1=1;
        largest=-1*max;
    }
    if(min>=0)
    {
        min1=1;
        smallest=-1*min;
    } 
    int hash1[largest+1];         // here I am creating the hashtable of length 100000000
    int hash2[(-1*smallest)+1];    
    i=0;
    for(;i<largest+1;i++)
    {
        hash1[i]=0;
    }
    i=0;
    for(;i<(-1*smallest)+1;i++)
    {
        hash2[i]=0;
    }
    i=0;
    for(;i<numsSize;i++)
    {
        if(nums[i]>=0)
        {
            hash1[nums[i]]++;
        }
        if(nums[i]<0)
        {
            hash2[(-1*nums[i])]++;
        }
    }
    i=0;
    for(;i<numsSize;i++)
    {
        if(nums[i]>=0)
        {
            hash1[nums[i]]--;
        }
        else
            if(nums[i]<0)
            {
                hash2[(-1*nums[i])]--;
            }
        if((target-nums[i])>=0)
        {
            if(max>0 && (target-nums[i])<=max)
            {
                if(hash1[target-nums[i]]>0)
                {
                   x=i;
                   y=target-nums[i];
                    break;
                }
            }
        }
        else
            if((target-nums[i])<0)
            {
                if(min<0 && (target-nums[i])>=min)
                {
                    if(hash2[-1*(target-nums[i])]>0)
                    {
                         x=i;
                         y=target-nums[i];
                         break;
                    }
                }
            }
    }
        *(returnSize)=2;
        i=0;
        int z=0;
        for(;i<numsSize;i++)
        {
            if(nums[i]==y)
            {
                z=i;
            }
        }
    int*p=(int*)malloc(2*sizeof(int));
    p[0]=x;
    p[1]=z;
    return p;
}
Posted
Updated 18-Oct-21 8:49am
v3
Comments
Richard MacCutchan 26-Jul-21 3:56am
   
What is this obsession with hash tables? All you need to do is loop through the list adding every number to every other number until you get the correct sum. A couple of simple loops.
_-_-_-me 27-Jul-21 7:14am
   
But , it takes O(n square ) complexity. They asked to find with less than O(n square) complexity .
Richard MacCutchan 27-Jul-21 7:21am
   
Well I still do not understand how you think a hash table will help.
_-_-_-me 28-Jul-21 11:02am
   
Whenever in the question if they asked to find the solution with less time complexity , I am always using hashmap with out knowing myself.
Because , I am only getting the hash map related idea.
If I think more and more and more... other than hash tag, days are being completed , I am taking 2 days for solving a question , then at last I am always being ended with hash tag.
How could we get the idea on algorithms with less time complexity ?
Thank you !
Richard MacCutchan 28-Jul-21 11:56am
   
Stop guessing, and find a good resource on algorithms, and study them. Google will find you many resources, and you will learn much faster than posting questions here.

This problem does not need to use a hash table because the answer has exactly two values in it. You need to calculate the set of your input data combined two at a time. You don't need to retain those values either. Just calculate them once and see if the answer matches. I would make a base 5 counter - however many input values you have, and step through each of them after making sure you don't have matching values. For 5 inputs you will have 25 values minus the possible matches. This amounts to retaining an array of two integers in addition to the input data. You can use nested for loops to do this.
   
Comments
_-_-_-me 26-Jul-21 0:02am
   
Sorry, I forgot to write the complete question .
In the question , they also given that to write the code with time complexity less than O(n square) .
Thank you!
Patrice T 26-Jul-21 0:23am
   
Use Improve question to update your question.
So that everyone can pay attention to this information.
_-_-_-me 26-Jul-21 0:31am
   
Okay .
Quote:
As a hash table of huge length would be created , does that much space available in memmory ?

Hash table, you did it again, already not the solution last time.
You are creating something with large cost to simplify another place of low cost, the result is more cost.
Solve this by hand nums = [2,7,11,15], target = 9
Do you need a hash table ?
Solve this by hand nums[]=[50000000,3,2,4,50000000] target=100000000
Do you need a hash table ?

Just checking every pair is in O(n)= n²

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

[Update]
Quote:
First sorting with time complexity less than O(n square) , and then take two variables , which should be acted as index .
These two indexes , one should start form beginning and other from last of the array .
If the sum is greater than the target , last variable should be decremented.
If the sum is less than target, then the first variable should be incremented...

It is basically the solution, try it ans see how it work.
   
v2
Comments
_-_-_-me 26-Jul-21 3:00am
   
Okay ,
when I solve this by hand ,
I am solving with the idea same as using the code which takes O(n square) complexity .
In that case , How could we know ?
How can we get the idea of algorithm as simple as possible ?

How could we know that algorithm is:
“Everything should be made as simple as possible, but no simpler.” Albert Einstein

I also got this idea:
First sorting with time complexity less than O(n square) , and then take two variables , which should be acted as index .
These two indexes , one should start form beginning and other from last of the array .
If the sum is greater than the target , last variable should be decremented.
If the sum is less than target, then the first variable should be incremented...

Thank you !
_-_-_-me 26-Jul-21 3:04am
   
When I solve this by hand,
I am doing it like this,
For every element of the array, I am calculating target-element, and then I am searching whether this value exists or not in the array .
But, this process is taking O(n square) time complexity .
_-_-_-me 26-Jul-21 3:07am
   
Does the solution also depends up on the language ?
Does the solution becomes easy when we know different language such as java, c++ ?
or
Does it not depend?

Thank you!
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    *returnSize=2;
    int *arr=(int *)malloc(2*sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[i]+nums[j]==target)
            {
                arr[0]=i;
                arr[1]=j;
                break;
            }
        }
    }
return arr;
   
Comments
Richard Deeming 19-Oct-21 4:25am
   
Looks like you missed the OP's requirement that the code "should be of time complexity less than O(n square)".

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900