TypeError: object() takes no parameters

I’m trying to do a coding challenge. In this challenge, they start you off with a class set up:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[ 0 ] + nums[ 1 ] = 2 + 7 = 9,
return [ 0 , 1 ].

I’m having trouble setting it up as a class. I understand what I’m supposed to return, but the class format makes it sketchy. I’m not sure if it wants you to create a class object or just set up the function or both.

Thanks
heres a link: https://leetcode.com/problems/two-sum/

This is not a solution, but it should give you some ideas…

Python 2 code

>>> from itertools import combinations as ncr
>>> class Solution:
	def __init__(self, nums, target):
		self.nums = nums
		self.target = target
	def two_nums(self):
		combs = ncr(self.nums, 2)
		return filter(lambda x: reduce(lambda a, b: a + b == self.target, x), combs)

	
>>> solve = Solution([2, 5, 8, 11, 15], 19)
>>> solve.two_nums()
[(8, 11)]
>>> 

It’s likely overkill and can be simplified. See what you can glean.

Note: In Python 3 reduce is in the functools module.


Further exploration

>>> class Solution:
	def __init__(self, nums, target):
		self.nums = nums
		self.target = target
	def indices(self, x):
		return [self.nums.index(i) for i in x[0]]
	def two_nums(self):
		combs = ncr(self.nums, 2)
		return self.indices(filter(lambda x: reduce(lambda a, b: a + b == self.target, x), combs))

	
>>> solve = Solution([2, 5, 8, 11, 15], 19)
>>> solve.two_nums()
[2, 3]
>>> 

Edit

Got rid of reduce.

>>> class Solution:
	def __init__(self, nums, target):
		self.nums = nums
		self.target = target
	def indices(self, x):
		return [self.nums.index(i) for i in x[0]]
	def match(self, x):
		return x[0] + x[1] == self.target
	def two_nums(self):
		combs = ncr(self.nums, 2)
		return self.indices(filter(self.match, combs))

	
>>> solve = Solution([2, 5, 8, 11, 15], 19)
>>> solve.two_nums()
[2, 3]
>>> 
>>> Solution([2, 5, 8, 11, 15], 19).two_nums()
[2, 3]
>>> 

Edit

BTW, still haven’t followed the link so this is seat of the pants stuff.


Edit

Got rid of the comprehension…

>>> class Solution:
	def __init__(self, nums, target):
		self.nums = nums
		self.target = target
	def indices(self, x):
		return [self.nums.index(x[0]), self.nums.index(x[1])]
	def match(self, x):
		return x[0] + x[1] == self.target
	def two_nums(self):
		combs = ncr(self.nums, 2)
		return self.indices(filter(self.match, combs)[0])

	
>>> Solution([2, 5, 8, 11, 15], 19).two_nums()
[2, 3]
>>> 
2 Likes

Interesting…

>>> class Solution:
	def __init__(self, nums, target):
		self.nums = nums
		self.target = target
		return self.two_nums()
	def indices(self, x):
		return [self.nums.index(x[0]), self.nums.index(x[1])]
	def match(self, x):
		return x[0] + x[1] == self.target
	def two_nums(self):
		combs = ncr(self.nums, 2)
		return self.indices(filter(self.match, combs)[0])

	
>>> Solution([2, 5, 8, 11, 15], 19)

Traceback (most recent call last):
  File "<pyshell#162>", line 1, in <module>
    Solution([2, 5, 8, 11, 15], 19)
TypeError: __init__() should return None
>>> 

Nice to know. Not the place to self-invoke. So where then?

2 Likes

Don’t worry about the class. You just need to write the body of the method. You don’t have to define any constructors or properties.

Imagine that you have to create function twoSum(nums, target). This is exactly the same.


@mtf this solution is quadratic in terms of time complexity. I know that you can do better! :slight_smile:

3 Likes

I’m curious about this, unable offhand to think of an approach that is not quadratic, at least in the worst-case. Any hints?

2 Likes

If the target is 7 and you find 3, what would the other one have to be? Is there one?

4 Likes

I was almost done with my elaborate, 3 paragraphs long answer :smiley: Thank you, I have much to learn from you!

4 Likes

Was it more or less spoilery? Now I’m curious
Maybe you were just stepping around it a bit more >.>

2 Likes

A bit more, unfortunately. I started explaining that it can be done with two passes or in a single pass through the list. Either way, I definitely prefer your version :slight_smile:

2 Likes

The instructions specifically stated that no element could be used more than once so I was sure my solution was way out in left field. Didn’t want to give away anything that would dissuade the member from seeking his own solution. Since it was mentioned that he didn’t know how to construct a class my example was more intended for that purpose. Pure silliness on the whole since it clearly broke that one crucial rule mentioned above.

2 Likes

petition to add haskell syntax highlighting around here

module TwoSum where

import           Data.Map.Strict                          ( (!) )
import qualified Data.Map.Strict               as Map

main :: IO ()
main = do
  nums   <- map read . words <$> getLine
  target <- read <$> getLine
  print $ twoSum nums target

twoSum :: [Integer] -> Integer -> Maybe (Int, Int)
twoSum xs' target = go (zip [0 ..] xs') Map.empty
 where
  go [] _ = Nothing
  go ((i, x) : xs) seen
    | complement `Map.member` seen = Just (seen ! complement, i)
    | otherwise                    = go xs (Map.insert x i seen)
    where complement = target - x

3 Likes

Sorry to be so obtuse, but if I ask the question, is the complement there? (linear), for each item in the list (also linear), is that not n^2 if the item & complement are at the end of the list?

2 Likes

Not exactly. You don’t have to check all the elements of the list. You can simply check if you already iterated through the complement. And as you probably know, there are data structures which allow you to check in the constant time if the given value exists in that data structure.

4 Likes

Overall, it is a single pass through the list.

Each time, bind x and i to the current value and its position, and also bind complement to target - x

After that, check whether the complement is in one of the values previously seen. if yes -> done, otherwise -> recurse with the rest of the list, add the current value/position to the seen ones

Directly translated to python it would be O(N) but the Map operations are O(log N) so it’s O(N log N) but that’s fine imo.

python approximation:

seen = {}
for i, x in enumerate(xs):
    complement = target - x
    if complement in seen:
        return (seen[complement], i)
    else:
        seen[x] = i
return None
4 Likes

Done, but don’t tell anyone, they do not appreciate Haskell :shushing_face: Clear cache and it should look a bit better.

2 Likes

That’s gorgeous, thank you.

3 Likes

Who are these people? I’ve come to quite enjoy haskell! After the few weeks bashing my head trying to think about things differently.


You could also go for a slightly different version. You could use Jonatan’s code but loop only through the numbers from 1 to the target and check if they are in the array, rather than looping through the arrays elements. This would create a program that grows with the target value rather than the length of the array. E.g. You could have an array of one hundred elements but the target value is 3.

2 Likes

But, negative numbers are allowed, right? :smiley:

2 Likes

pic or no proof

3 Likes

Ah perhaps I have oversimplified the problem! In a new version I’d the challenge with that limitation then we could use my version.

But these are the sort of challenges I’d love to see in a fortnightly feature. I think the current challenges are perhaps not technical enough to get people really interested and trying novel ideas

2 Likes