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

3 views (last 30 days)
Lysette on 10 May 2023
Commented: Dyuman Joshi on 11 May 2023
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

Dyuman Joshi on 10 May 2023
Edited: Dyuman Joshi on 10 May 2023
(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
##### 2 CommentsShow 1 older commentHide 1 older comment
Dyuman Joshi on 11 May 2023
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

Steven Lord on 10 May 2023
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 on 10 May 2023
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?