admin管理员组文章数量:1327739
So this is the problem given.
Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:
There is 1 smaller element to the right of 3
There is 1 smaller element to the right of 4
There are 2 smaller elements to the right of 9
There is 1 smaller element to the right of 6
There are no smaller elements to the right of 1
I came up with this two pointer algorithm.
function lessThan(arr) {
let results = [];
let i = 0;
let j = arr.length - 1;
let count = 0;
while (i < arr.length) {
if (arr[i] > arr[j]) {
count++;
}
j--;
if (j === 1) {
results.push(count);
count = 0;
i++;
j = arr.length - 1;
}
}
return results;
}
the pointer 'i' will start at the begining and 'j' will start at the end. if 'j' is equal to 1.'i' gets incremented and 'j' reset to the end. This goes on untill 'i' reaches the end of the array.(when 'i' is equal or greater than arr.length the while loop breaks). According to what I know about time plexity.I guess as we go through the array only once it is O(n). But shouldnt we be considering the fact that there are 'n' parisions made with respect to 'j' as we go through? I am new to petitive programming and Big O notation.Please help me out.
Thank you.
So this is the problem given.
Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:
There is 1 smaller element to the right of 3
There is 1 smaller element to the right of 4
There are 2 smaller elements to the right of 9
There is 1 smaller element to the right of 6
There are no smaller elements to the right of 1
I came up with this two pointer algorithm.
function lessThan(arr) {
let results = [];
let i = 0;
let j = arr.length - 1;
let count = 0;
while (i < arr.length) {
if (arr[i] > arr[j]) {
count++;
}
j--;
if (j === 1) {
results.push(count);
count = 0;
i++;
j = arr.length - 1;
}
}
return results;
}
the pointer 'i' will start at the begining and 'j' will start at the end. if 'j' is equal to 1.'i' gets incremented and 'j' reset to the end. This goes on untill 'i' reaches the end of the array.(when 'i' is equal or greater than arr.length the while loop breaks). According to what I know about time plexity.I guess as we go through the array only once it is O(n). But shouldnt we be considering the fact that there are 'n' parisions made with respect to 'j' as we go through? I am new to petitive programming and Big O notation.Please help me out.
Thank you.
Share Improve this question edited Aug 3, 2020 at 3:18 Sascha A. 4,6363 gold badges16 silver badges34 bronze badges asked Aug 2, 2020 at 17:48 Sai DarshanSai Darshan 3874 silver badges15 bronze badges 6- I don't see how you can do that in a way that's not ultimately O(n^2) – Pointy Commented Aug 2, 2020 at 17:51
-
@Pointy I'm pretty certain you can do in
O(n log n)
if you keep a sorted array and traverse the input from right to left. – Bergi Commented Aug 2, 2020 at 17:55 - No you cannot @Bergi.If you sort it .For 9 there will be 4 elements lesser than it.But if you read the problem description.That would result it in a wrong answer – Sai Darshan Commented Aug 2, 2020 at 18:06
- 1 There might be a "dynamic programming" approach (if that term is still in use 40 years after I learned it) that would work, but I can never figure those out. – Pointy Commented Aug 2, 2020 at 18:12
-
1
@Pointy This isn't really a dynamic programming problem. It's very similar to the problem of counting inversions, and can be done in
O(n log n)
. – Unmitigated Commented Mar 4, 2024 at 2:34
2 Answers
Reset to default 4It is O(n²), you increment i
every len(arr)
iterations, and so until i
reach len(arr)
.
That give a plexity in len(arr) * len(arr)
i.e. O(n²).
You can rearrange your code to
function lessThan(arr) {
let results = [];
let i = 0;
while (i < arr.length) {
let j = arr.length - 1;
let count = 0;
while (j !== 1) {
if (arr[i] > arr[j]) {
count++;
}
j--;
}
results.push(count);
i++;
}
return results;
}
Yes, you've cleverly merged the nested loops into a single one, but that doesn't change its plexity. Notice that in your version, the while
loop runs arr.length ²
times, as i
is not incremented on every iteration but only when j == 1
.
From my updated version it's not only clearly visible that the code is O(n²)
, but also that it's wrong: j !== 1
(or j > 1
) should pare to i
instead of 1
- you only want to count the elements on the right.
本文标签: javascriptTime complexity of algorithms using two pointersIs it 0(n) or 0(n2)Stack Overflow
版权声明:本文标题:javascript - Time complexity of algorithms using two pointers.Is it 0(n) or 0(n^2) - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1742228453a2436767.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论