-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path0442.py
More file actions
94 lines (61 loc) · 2.08 KB
/
Copy path0442.py
File metadata and controls
94 lines (61 loc) · 2.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
"""
# 422. Find All Duplicates in an Array
- https://leetcode.com/problems/find-all-duplicates-in-an-array/
- Classification: Arrays
## Challenge
Given an integer array nums of length n
where all the integers of nums are in the range [1, n]
and each integer appears once or twice,
Return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time
and uses only constant extra space.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Example 2:
Input: nums = [1,1,2]
Output: [1]
Example 3:
Input: nums = [1]
Output: []
Constraints:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.
## Solution
Due to the constrainst of this problem
any value-1 can be used as an index pointer.
This way highest number in the array will never
exceed the length of the array index.
Example of a possible array showcasing the index -1 case:
index: 0 1 2 3
array: [1, 2, 4, 4]
Solution: loop over the array
- use the absolute value -1 as an index
- multiply the value at that index with -1 if it is positive or:
- if the value at the index is already negative: a double is found
Alternative:
- use the absolute value -1 as an index
- multiply the value at that index with -1
- if the value at the index is positive that means double negation and a double is found
- This only works if an alement can not appear 3 or more times
"""
class Solution:
def findDuplicates(self, nums: list[int]) -> list[int]:
duplicates = []
for index in range(len(nums)):
# grab the absolute value
value = abs(nums[index])
# use the value -1 as an index
# check if the number was altered before
# with the negative sign check
if nums[value -1] > 0:
nums[value -1] *= -1
else:
duplicates.append(value)
return duplicates
if __name__ == "__main__":
s = Solution()
# print(s.findDuplicates([1, 2, 4, 3, 1]))
print(s.findDuplicates([4,3,2,7,8,3,2,1,5,7]))