Leetcode: Detecting duplicate elements in an array within a k-element windowLeetcode Mountain ArrayFaster...
Is a vector space a subspace?
Information to fellow intern about hiring?
How would photo IDs work for shapeshifters?
Is this food a bread or a loaf?
Can I find out the caloric content of bread by dehydrating it?
Pristine Bit Checking
What is GPS' 19 year rollover and does it present a cybersecurity issue?
What to wear for invited talk in Canada
Is there a familial term for apples and pears?
How to answer pointed "are you quitting" questioning when I don't want them to suspect
How can I fix this gap between bookcases I made?
Was there ever an axiom rendered a theorem?
Can the Produce Flame cantrip be used to grapple, or as an unarmed strike, in the right circumstances?
If a centaur druid Wild Shapes into a Giant Elk, do their Charge features stack?
Calculate Levenshtein distance between two strings in Python
Is ipsum/ipsa/ipse a third person pronoun, or can it serve other functions?
What causes the sudden spool-up sound from an F-16 when enabling afterburner?
Why is the design of haulage companies so “special”?
Could Giant Ground Sloths have been a good pack animal for the ancient Mayans?
What does it exactly mean if a random variable follows a distribution
What does "enim et" mean?
Typesetting a double Over Dot on top of a symbol
Where to refill my bottle in India?
"listening to me about as much as you're listening to this pole here"
Leetcode: Detecting duplicate elements in an array within a k-element window
Leetcode Mountain ArrayFaster code for leetcode reverse intHash table solution to twoSumA One-Pass Hash Table Solution to twoSumIn an set of integers, find three elements summing to zero (3-sum, leetcode variant)In place solution to remove duplicates from a sorted listthe memory usage to “CourseSchedule” algorithmsKahn's algorithms to arrange CouseScheduleTwo solutions to leetcode 127.wordLadderKadane's algorithms to leetcode “121 Best Time to Buy and Sell Stock”
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
Upon solving the problem 'contain duplicates` in leetcode:
Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .
Example 1:
Input: nums = [1,2,3,1] , k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1] , k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3] , k = 2
Output: false
I tried best to write a Pythonic style solution and improve the performance.
class Solution2:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
lookup = dict() #{value:index}
for cur, val in enumerate(nums):
prev = lookup.get(val)
if prev != None and cur - prev <= k:
#logging.debug(f"{cur - prev}")
return True
lookup[val] = cur #add it to lookup
return False
Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.
I am confused about the score. I was 100% assure that it was the best possible solution.
What's the problem with my solution?
python performance programming-challenge
edited yesterday
200_success
131k17157422
asked yesterday
AliceAlice
3206
$endgroup$
add a comment |
$begingroup$
Upon solving the problem 'contain duplicates` in leetcode:
Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .
Example 1:
Input: nums = [1,2,3,1] , k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1] , k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3] , k = 2
Output: false
I tried best to write a Pythonic style solution and improve the performance.
class Solution2:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
lookup = dict() #{value:index}
for cur, val in enumerate(nums):
prev = lookup.get(val)
if prev != None and cur - prev <= k:
#logging.debug(f"{cur - prev}")
return True
lookup[val] = cur #add it to lookup
return False
Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.
I am confused about the score. I was 100% assure that it was the best possible solution.
What's the problem with my solution?
python performance programming-challenge
edited yesterday
200_success
131k17157422
asked yesterday
AliceAlice
3206
$endgroup$
add a comment |
$begingroup$
Upon solving the problem 'contain duplicates` in leetcode:
Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .
Example 1:
Input: nums = [1,2,3,1] , k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1] , k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3] , k = 2
Output: false
I tried best to write a Pythonic style solution and improve the performance.
class Solution2:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
lookup = dict() #{value:index}
for cur, val in enumerate(nums):
prev = lookup.get(val)
if prev != None and cur - prev <= k:
#logging.debug(f"{cur - prev}")
return True
lookup[val] = cur #add it to lookup
return False
Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.
I am confused about the score. I was 100% assure that it was the best possible solution.
What's the problem with my solution?
python performance programming-challenge
edited yesterday
200_success
131k17157422
asked yesterday
AliceAlice
3206
$endgroup$
Upon solving the problem 'contain duplicates` in leetcode:
Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .
Example 1:
Input: nums = [1,2,3,1] , k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1] , k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3] , k = 2
Output: false
I tried best to write a Pythonic style solution and improve the performance.
class Solution2:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
lookup = dict() #{value:index}
for cur, val in enumerate(nums):
prev = lookup.get(val)
if prev != None and cur - prev <= k:
#logging.debug(f"{cur - prev}")
return True
lookup[val] = cur #add it to lookup
return False
Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.
I am confused about the score. I was 100% assure that it was the best possible solution.
What's the problem with my solution?
python performance programming-challenge
python performance programming-challenge
edited yesterday
200_success
131k17157422
asked yesterday
AliceAlice
3206
edited yesterday
200_success
131k17157422
asked yesterday
AliceAlice
3206
edited yesterday
200_success
131k17157422
edited yesterday
200_success
131k17157422
edited yesterday
200_success
131k17157422
131k17157422
asked yesterday
AliceAlice
3206
asked yesterday
AliceAlice
3206
asked yesterday
AliceAlice
3206
3206
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an $(O(n))$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with $O(k))$.
It makes no difference if $k approx n$, but boosts the performance for $k ll n$ (which I presume is so for the bulk of test cases).
To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.
answered yesterday
vnpvnp
40.7k233103
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217008%2fleetcode-detecting-duplicate-elements-in-an-array-within-a-k-element-window%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an $(O(n))$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with $O(k))$.
It makes no difference if $k approx n$, but boosts the performance for $k ll n$ (which I presume is so for the bulk of test cases).
To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.
answered yesterday
vnpvnp
40.7k233103
$endgroup$
add a comment |
$begingroup$
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an $(O(n))$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with $O(k))$.
It makes no difference if $k approx n$, but boosts the performance for $k ll n$ (which I presume is so for the bulk of test cases).
To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.
answered yesterday
vnpvnp
40.7k233103
$endgroup$
add a comment |
$begingroup$
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an $(O(n))$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with $O(k))$.
It makes no difference if $k approx n$, but boosts the performance for $k ll n$ (which I presume is so for the bulk of test cases).
To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.
answered yesterday
vnpvnp
40.7k233103
$endgroup$
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an $(O(n))$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with $O(k))$.
It makes no difference if $k approx n$, but boosts the performance for $k ll n$ (which I presume is so for the bulk of test cases).
To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.
answered yesterday
vnpvnp
40.7k233103
answered yesterday
vnpvnp
40.7k233103
answered yesterday
vnpvnp
40.7k233103
answered yesterday
vnpvnp
40.7k233103
40.7k233103
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217008%2fleetcode-detecting-duplicate-elements-in-an-array-within-a-k-element-window%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
