Find All Duplicates In An Array

                                            
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        for (int num : nums) {
            int index = abs(num) - 1;
            if (nums[index] < 0) {
                result.push_back(abs(num));
            } else {
                nums[index] *= -1;
            }
        }
        return result;
    }
};

                                            
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            if (nums[index] < 0) {
                result.add(Math.abs(num));
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }
}

                                            
class Solution:
    def findDuplicates(self, nums):
        result = []
        for num in nums:
            index = abs(num) - 1
            if nums[index] < 0:
                result.append(abs(num))
            else:
                nums[index] *= -1
        return result

                                            
/**
 * Note: The returned array must be malloced, assume caller 
   calls free().
 */
int* findDuplicates(int* nums, int numsSize, int* returnSize){
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int index = abs(nums[i]) - 1;
        if (nums[index] < 0) {
            result[(*returnSize)++] = abs(nums[i]);
        } else {
            nums[index] = -nums[index];
        }
    }
    
    return result;
}

                                            
public class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        List<int> result = new List<int>();
        
        for (int i = 0; i < nums.Length; i++) {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] < 0) {
                result.Add(index + 1);
            } else {
                nums[index] = -nums[index];
            }
        }
        
        return result;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function(nums) {
    let result = [];
    
    for (let num of nums) {
        let index = Math.abs(num) - 1;
        if (nums[index] < 0) {
            result.push(index + 1);
        } else {
            nums[index] *= -1;
        }
    }
    
    return result;
};

                                            
function findDuplicates(nums: number[]): number[] {
    const result: number[] = [];
    for (let num of nums) {
        const index = Math.abs(num) - 1;
        if (nums[index] < 0) {
            result.push(index + 1);
        } else {
            nums[index] *= -1;
        }
    }
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function findDuplicates($nums) {
        $result = [];
        foreach ($nums as $num) {
            $index = abs($num) - 1;
            if ($nums[$index] < 0) {
                $result[] = $index + 1;
            } else {
                $nums[$index] *= -1;
            }
        }
        return $result;
    }
}

                                            
class Solution {
    func findDuplicates(_ nums: [Int]) -> [Int] {
        var result: [Int] = []
        
        var nums = nums
        
        for num in nums {
            let index = abs(num) - 1
            if nums[index] < 0 {
                result.append(index + 1)
            }
            nums[index] = -nums[index]
        }
        
        return result
    }
}

                                            
class Solution {
    fun findDuplicates(nums: IntArray): List<Int> {
        val result = mutableListOf<Int>()
        for (num in nums) {
            val index = Math.abs(num) - 1
            if (nums[index] < 0) {
                result.add(index + 1)
            } else {
                nums[index] = -nums[index]
            }
        }
        return result
    }
}

                                            
class Solution {
  List<int> findDuplicates(List<int> nums) {
    List<int> result = [];
    
    for (int num in nums) {
      int index = num.abs() - 1;
      if (nums[index] < 0) {
        result.add(index + 1);
      } else {
        nums[index] *= -1;
      }
    }
    
    return result;
  }
}

                                            
func findDuplicates(nums []int) []int {
    result := []int{}
    
    for _, num := range nums {
        index := abs(num) - 1
        if nums[index] < 0 {
            result = append(result, abs(num))
        } else {
            nums[index] *= -1
        }
    }
    
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

                                            
# @param {Integer[]} nums
# @return {Integer[]}
def find_duplicates(nums)
    result = []
    nums.each do |num|
        index = num.abs - 1
        if nums[index] < 0
            result << index + 1
        else
            nums[index] *= -1
        end
    end
    result
end

                                            
object Solution {
    def findDuplicates(nums: Array[Int]): List[Int] = {
        val result = scala.collection.mutable.ListBuffer[Int]()
        
        for (num <- nums) {
            val index = Math.abs(num) - 1
            if (nums(index) < 0) {
                result += index + 1
            } else {
                nums(index) = -nums(index)
            }
        }
        
        result.toList
    }
}

                                            
impl Solution {
    pub fn find_duplicates(nums: Vec<i32>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut nums = nums;
        
        for i in 0..nums.len() {
            let index = (nums[i].abs() - 1) as usize;
            if nums[index] < 0 {
                result.push(nums[i].abs());
            } else {
                nums[index] *= -1;
            }
        }
        
        result
    }
}

                                            
(define/contract (find-duplicates nums)
  (-> (listof exact-integer?) (listof exact-integer?))
  (define seen (make-vector (+ (length nums) 1) 0))
  (define result '())
  
  (for ([num nums])
    (if (= (vector-ref seen num) 1)
        (set! result (cons num result))
        (vector-set! seen num 1)))
  
  result
)

                                            
-spec find_duplicates(Nums :: [integer()]) -> [integer()].
find_duplicates(Nums) ->
    Result = lists:map(fun(_) -> 0 end, Nums),
    find_duplicates(Nums, Result, []).

find_duplicates([], _, Result) ->
    lists:reverse(Result);
find_duplicates([H|T], Seen, Result) ->
    case lists:nth(H, Seen) of
        0 -> find_duplicates(T, lists:sublist(Seen, H-1) ++ [1] ++ lists:nthtail(H, Seen), Result);
        1 -> find_duplicates(T, Seen, [H|Result])
    end.

                                            
defmodule Solution do
  @spec find_duplicates(nums :: [integer]) :: [integer]
  def find_duplicates(nums) do
    Enum.reduce(nums, {[], %{}}, fn x, {duplicates, seen} ->
      if Map.get(seen, x, 0) == 1 do
        {[x | duplicates], seen}
      else
        {duplicates, Map.put(seen, x, 1)}
      end
    end)
    |> elem(0)
    |> Enum.reverse()
  end
end

To solve this coding challenge, we need to identify the integers in an array that appear exactly twice. The constraints specify that we need an algorithm with a time complexity of O(n) and constant extra space. Let's break down the problem and the solution step by step.

Explanation

The given integer array

nums

consists of integers ranging from 1 to n and each integer appears either once or twice. The goal is to return an array of all the integers that appear twice. Here's how we can achieve the solution with the given constraints:

Utilize Indexing for Marking: We can use the array itself to keep track of which numbers have been seen once. By marking visited numbers using negative signs, we can identify duplicates.
Marking Steps:

Iterate through each number in the array.
For each number, calculate its corresponding index by taking the absolute value of the number and subtracting one (since the numbers are 1-based, and array indices are 0-based).
Check if the number at this index is negative. If it is, it means the number corresponding to this index has already been visited, indicating a duplicate.
If the number at this index is not negative, mark the number at this index as visited by making it negative.

Collect the Duplicates: When we encounter a number that points to an already marked index (negative value), we add it to the result list as it signifies a duplicate.

This approach ensures that we are only using constant extra space (aside from the input and output) and that we are processing each element of the array once, making the time complexity O(n).

Step-by-Step Explanation / Detailed Steps in Pseudocode

Initialize an empty result list.
Iterate over each number in the input array (nums).
For each number, compute the corresponding index in the array:

Calculate the index as the absolute value of the number minus one.

Check the sign of the number at the computed index:

If the number at this index is negative, this means the current number is a duplicate.
If the number at this index is positive, mark it as visited by making it negative.

If a duplicate is found (step 4's negative check), add the absolute value of the current number to the result list.
Return the result list containing all duplicates.

Now, let's write the pseudocode with comments integrated for each of these steps:

                                            
# Function to find duplicates in an array
function findDuplicates(nums):
    # Initialize an empty list to store duplicates
    duplicates = []
    
    # Iterate through each number in the array
    for each number in nums:
        # Calculate the corresponding index (convert to zero-based index)
        index = absolute value of number - 1
        
        # Check if the number at this index is negative
        if nums[index] < 0:
            # If so, it is a duplicate and add its absolute value to the result list
            append absolute value of number to duplicates
        else:
            # Otherwise, mark the number at this index as visited (turn it negative)
            nums[index] = -nums[index]
    
    # Return the list of duplicates found
    return duplicates

By following this pseudocode, you will achieve the desired solution with the given constraints: O(n) time complexity and constant extra space. This detailed step-by-step explanation ensures clarity on each action taken to derive the result while maintaining the efficiency of the algorithm.