How can I change my O(n^2) solution to O(n logn) or better?

My inputs are an integer array and an integer target. Two numbers in the array add up to the target, and I need to return the indices of these numbers. The code is set to time out if it is not efficient enough.

For example, if num_array = [2 7 11 15] and target = 9, the answer would be [1 2], since num_array(1) + num_array(2) = 9.

I have a solution that works for small and medium arrays, but it is of order O(n^2) and times out for very large arrays. To work for all cases, my solution needs to be better than O(n^2), so at least O(nlogn). All the ways I can think of solving this need to iterate through the array twice. This is my code so far:

function [i,j] = mySum(nums, target)
   for n = 1:length(nums)
        aim = target - nums(n); % find the sum counterpart
        % search for it in the array
        idx = find(nums(n+1:end) == aim, 1) + n;
        if (length(idx) == 0)
            % no solution found
            continue
        else
            % solution found
            i = n; j = idx;
            break
        end
    end    
end

Any advice would be greatly appreciated. Thank you in advance.

Answer 1

[Dyuman Joshi]

(Assuming you are working with a vector and finding the first pair whose sum is equal to the target)

Use logical indexing in the initial step and then use find()

arr = [2 7 11 15];
t = 9;
fun1 = @(x,y) mySumoriginal(x,y);
fun2 = @(x,y) mySummodified(x,y);
f1 = @() fun1(arr,t);
f2 = @() fun2(arr,t);

%Checking if outputs are equal or not
isequal(f1(),f2())

ans = logical
   1

fprintf('Time taken by original function = %f seconds', timeit(f1))

Time taken by original function = 0.000088 seconds

fprintf('Time taken by modified function = %f seconds', timeit(f2))

Time taken by modified function = 0.000006 seconds

The modified function is more than 14 times faster!

function [i,j] = mySumoriginal(nums, target)
   for n = 1:length(nums)
        aim = target - nums(n); % find the sum counterpart
        % search for it in the array
        idx = find(nums(n+1:end) == aim, 1) + n;
        if (length(idx) == 0)
            % no solution found
            continue
        else
            % solution found
            i = n; j = idx;
            break
        end
    end    
end


function [i,j] = mySummodified(nums, target)
   for n = 1:length(nums)
        aim = target - nums(n); % find the sum counterpart
        %check if any number satisfies the condition
        idx = nums(n+1:end) == aim;
        if any(idx)
            % solution found
            i = n; j = find(idx,1)+n;
            break
        end
    end    
end

There is a vector method as well (written below), which is comparable to the modified function, but it will require more memory for larger arrays.

function [c,r] = mySumvector(arr,t)
%Indexing in MATLAB is column wise
[r,c]=find(arr+arr'==t,1);
end

[Lysette]

Thank you very much for your solution, it is much more efficient than mine! I haven't tested out the vector method yet but I will give that a go as well.

I also didn't know that there was a MATLAB function that measures the time taken to run a function, which could have made some of my past programs much easier to optimise. Thank you :)

[Dyuman Joshi]

In the context of your comment on Steven's Answer, the vector approach needs a slight modification and is a quite slower (Although, this might not be the the best approach to vectorization here)

However, Loops are quite efficient when used properly, which you can observe here

arr=randi(20,1,1000);
t=13;

fun1 = @(x,y) mySumoriginal(x,y);
fun2 = @(x,y) mySummodified(x,y);
fun3 = @(x,y) mySumvector(x,y);
f1 = @() fun1(arr,t);
f2 = @() fun2(arr,t);
f3 = @() fun3(arr,t);

%Checking if outputs are equal or not
isequal(f1(),f2(),f3())

ans = logical
   1

fprintf('Time taken by original function = %f seconds', timeit(f1))

Time taken by original function = 0.000081 seconds

fprintf('Time taken by modified function = %f seconds', timeit(f2))

Time taken by modified function = 0.000007 seconds

fprintf('Time taken by vector function = %f seconds', timeit(f3))

Time taken by vector function = 0.001338 seconds

function [i,j] = mySumoriginal(nums, target)
   for n = 1:length(nums)
        aim = target - nums(n); % find the sum counterpart
        % search for it in the array
        idx = find(nums(n+1:end) == aim, 1) + n;
        if (length(idx) == 0)
            % no solution found
            continue
        else
            % solution found
            i = n; j = idx;
            break
        end
    end    
end


function [i,j] = mySummodified(nums, target)
   for n = 1:length(nums)
        aim = target - nums(n); % find the sum counterpart
        %check if any number satisfies the condition
        idx = nums(n+1:end) == aim;
        if any(idx)
            % solution found
            i = n; j = find(idx,1)+n;
            break
        end
    end    
end

function [c,r] = mySumvector1(arr,t)
z=(arr+arr').*(1-eye(numel(arr)));
[r,c]=find(z==t,1);
end

Answer 2

[Steven Lord]

You don't need to create a big matrix, just another vector.

num_array = [2 7 11 15]

num_array = 1×4

2 7 11 15

target = 9

target = 9

solutionLocations = ismember(num_array, target-num_array)

solutionLocations = 1×4 logical array
   1   1   0   0

[num_array(solutionLocations); target-num_array(solutionLocations)]

ans = 2×2

2 7 7 2

[Lysette]

Thank you, this is a really efficient solution and it seemed to be working well! However, after a few tests I noticed it fails in cases like this one:

num_array = [3,2,4];
target = 6;

solutionLocations = ismember(num_array, target-num_array)

solutionLocations = 1×3 logical array
   1   1   1

a = find(solutionLocations, 2)

a = 1×2

1 2

Since there is a 3 in both num_array and target-num_array, it presents this as a solution, when the only real solution is a = [2 3].

I added in a few lines that effectively made solutionLocations(i) = 0 where num_array(i) == target(num_array), but this fails in cases like num_array = [5 5], target = 10. I hope my description of the problem is clear.

Very grateful for the advice so far, but do you have any suggestions on how I could fix this?