Tag Info

15

Looking at your code, this jumps out at me: D = {} for x in range(n): if complement in D.values(): The D variable here is a dictionary. It is designed for $O(1)$ lookup of a key. But you are looping over n items, performing a test (complement in D.values()) that is $O(m)$ itself, since D.values() is an iterable and the in test will be ...

13

Code Style Your code contains a few lines that accomplish nothing and obfuscate your intent: else: continue If the conditional is false, you'll automatically continue on to the next iteration without having to tell the program to do that. return None All Python functions implicitly return None. While PEP 8 appears to endorse this ...

11

Not quite right First off, you're checking every cross pair of indices against each other. But that means that findTwoSum({1, 3, 4}, 6) will succeed, even though there is no pair of elements that sum to 6 - because you count the 3 twice. You need: "any two distinct elements". Iterating over vectors list is a confusing name for a vector. increment is a ...

10

Most C# developers will place opening braces on a new line. If you do this as well then you make it easier to read the code by others. complement and index should use var "type" as well twoSumSolution isn't really needed and is only adding noise to the code. I like to use if (bool == false) instead of if (!bool) because I can grasp it at first glance ...

10

Removing numbers greater than the target affects the correctness of this program - they could be added to negative numbers to reach the target. You could get a performance improvement by finding the difference between each element and the target, then looking to see if that difference is in the list. This doesn't in itself reduce the computational ...

8

There's a failing case you might have missed. If the target number is exactly twice the value of one of the entries, then you'll wrongly return true. Test case: anyequalto([5], 10) Besides that, try to think of a better name for the function. Perhaps contains_pair_totalling() as a start?

8

The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique doesn't look correct; it is prone to false positives). There are few standard ways to bring the ...

8

You are using one explicit pass over the list (for i in list), and one implicit pass over the list (k - i in list). This means your algorithm is $O(N^2)$. Note: You can reduce your implementation to one line: return any(k - i in list for i in list) But you have a bug. is_sum_of_2nums_in_list_k([5], 10) returns True. A one pass algorithm starts with ...

8

First some stylistic points nums_d.setdefault(nums[i], []).append(i) The setdefault is unnecessary here, you can assign a list normally nums_d[nums[i]] = [i] When you need both the index and the element use enumerate see PEP279 nums_d = {} for i in range(len(nums)): nums_d.setdefault(nums[i], []).append(i) nums_d = {} for i, e in enumerate(nums): ...

8

Your bi_search() method is recursive. It doesn’t have to be. Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop. Instead of if len(L) < 1:, use a while len(L) > 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call. Better: don’t modify L at all, which involves copying a list of ...

7

I see some things that may help your improve your program. Think about a better algorithm At the moment, for each item in the list, the code looks for a matching number in the entire list. This is ${\bf O}(n^2)$ complexity. First, the inner loop could at least start with the next element instead of starting from 0. That would save a little time and is ...

7

Just a few tips about your PrepareKey method. private static string PrepareKey(int[] arr, int length) { string key = string.Empty; for (int j = 0; j < length; j++) { key += arr[j].ToString(); key += ","; } return key; } The entire function can be replaced with: string.Join(",", arr); but in cases where you need to build a ...

6

if (nums == null || nums.Length == 0) return results; should be if (nums == null || nums.Length < 3) return results; another List<int> threeNumbers = new List<int> { firstNo, nums[start], nums[end] }; string key = PrepareKey(string.Join(",", threeNumbers); if (!keys.Contains(key)) { keys.Add(key); ...

6

Formatting The indenting and placement of braces is inconsistent in the program, and it hurts readability. Instead of this: for(int i = first_i ; i< list.Count; i++) { for(int j=second_i; j<list.Count; j++) { if(i != list.Count) { global_sum += list[i] + ...

6

So far every solution given has been O(n2) or O(n log n), but there is an O(n) solution, which is sketched as follows: Get your input into a list, as you have done so. Obviously this is O(n) Create an empty map from integers to integers. The map must have an O(1) insertion operation and an O(1) contains-key operation and an O(1) lookup operation and an O(n) ...

6

Return value Adding a few tests, we have: print(anyequalto([10, 15, 3, 7], 17)) print(anyequalto([10, 15, 3, 7], 18)) print(anyequalto([10, 15, 3, 7], 19)) giving True True None The None value seems a bit unexpected to me. We'd probably want False to be returned in that particular case. Also, even if you expect None to be returned in that case, the ...

5

Some minor points: 1) You don't really need the complement variable, so just do the math in the call to TryGetValue(). 2) If int[] nums are all positive you may continue the loop if nums[i] > target. 3) It is stated that there is only one solution per input, so you can skip the check if (!numsDictionary.ContainsKey(nums[i])). This will never be true ...

5

Normally, we'd use the vector's index type (std::vector<int>::size_type, i.e. std::size_t) for the return values. But unfortunately we're required to return negative values when the search fails, so I'd recommend a pair of std::ptrdiff_t instead. And the question specifically asks for ints, so I'd just insert a comment explaining that were limited to ...

5

num_lst = list(range(len(nums))) for indx, num in enumerate(num_lst): I'm not sure if I'm missing something, but I think not. I ran this code nums = [2,5,7,9] num_lst = list(range(len(nums))) list(enumerate(num_lst)) output : [(0, 0), (1, 1), (2, 2), (3, 3)] So why do you create the list and then enumerate it? Maybe what you want to do is simply : ...

5

Code "When all you have is a hammer, everything looks like a nail." Your tool chest seems to have dict, which you are using to implement a container which doesn't contain any duplicates. There is a name for that tool. It is called as set. Study it; you will find it very useful. Consider: nums_dict = {} for indx, val in enumerate(nums_small, ...

5

(Quick note: please do not use list as a variable name, as it's also the name of a type. I'm going to use list_ instead) Depending on the interpretation, it could be that they want you to iterate over the list just once. The statement "v in list" potentially iterates over the full list, which means it's yet another pass. If you know nothing about the list,...

4

Avoid unnecessary memory allocations. Memory allocations take time, significant time if you do them in your inner most loop. For starters, change: vector<vector<int>> output; to: vector<std::tuple<int, int, int>> output; This converts your putput vector from "A vector of pointers to fixed size dynamic elements" (note the ...

4

The O(n²) approach The first algorithm is indeed O(n²), because, for every element in the array, the array is traversed again to see whether an element after the current element is equal to 10 minus it. It is quite clear, and there is not much to change. Comments are: There is a bug: you're checking the same element twice in a row, since j, in the inner ...

4

Typo in method name as pointed out by @Stingy. Should be findAllPairs. Accessing wrong array: You are reading values from input instead of your sorted copy numbers. This is probably a typo. E.g. int sum = input[low] + input[high]; should be int sum = numbers[low] + numbers[high]; Your for loop has an empty update statement, this isn't wrong per-se but a bit ...

4

As 200_success mentions, your solution is $O(n^2)$, due to the double for loop. You actually have an error in your inner loop. You start the inner loop with for (int k = i; ..., but it should be for (int k = i + 1; .... This means you could return true for an even expected sum when half of that value appears once in the list. If you correct the above ...

4

Lists are pretty inefficient for this type of thing. The majority of the complexity is from iterating over the lists and comparing contents. Sets use a hash for their content, reducing complexity. When using sets, most of the complexity comes from the combinations function. Here are the results of a time test on your code res1 = Solution().fourSum([-5,5,4,...

4

// init const arr = [1, 2, 3, 4, 5]; const K = 9; // main const getContiguousElementsSum = (arr, K) => { It seems to me to be unnecessarily confusing to alias variable identifiers like this. if (arr.length === 0 || K < 0) { return null; } I don't see this anywhere in the specification you've quoted. I would expect the function to handle K ==...

4

AlexV has covered the formatting stuff. With regards to the length and efficiency of the code: You've clearly put a lot of thought into how to calculate the list of tuples requested. And you've found some good efficiencies! But you're approaching this from the wrong direction: Start with the clearest syntactically legal expression of the desired result you ...

3

From a review of your code, I see that you loop over your input in a nested for loop. This is actually not required to solve the problem. Instead, create one hashset for every number in your numbers array, and another hashset for every number in numbers + k. Then we only have to check for intersections. This should take your $O(n^2)$ algorithm and turn ...

3

I think your solution is already pretty good. It is at worst $\mathcal{O}(n)$ in both runtime and memory. You use enumerate instead of iterating over the indicies manually. The only four things I would comment on are: In real life code, this being a class would of course be completely unnecessary (but it seems to be mandatory in this case). Explicitly ...

Only top voted, non community-wiki answers of a minimum length are eligible