Data Structure & Algorithms
  • šŸ–ŒļøUnlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Two Sum

Array, Hash Table

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints and Statements:

  • Input: Array of integers nums and an integer target.

  • Output: Indices of the two numbers that add up to target.

Assumptions:

  • Each input has exactly one solution.

  • The same element cannot be used twice.

  • The answer can be returned in any order.

Questions to Clarify:

  • Negative Numbers: Can the input array contain negative numbers? No.

  • Duplicate Numbers: Can the input array contain duplicate numbers? No.

  • Unique Solution: Is it guaranteed that there will always be exactly one solution? No.

  • Multiple Solutions: Should we return all possible solutions, or just one? No.

  • Indices Required: Do we need to return the actual indices of the solution numbers, or just the numbers themselves? Actual indices of the solution numbers.

Additional Considerations:

  • Array Size: What are the expected size limits for the input array?

  • Time and Space Complexity: Are there any specific time or space complexity requirements for the solution?

  • Algorithm Choice: Would a specific algorithm (e.g., hash table-based or sorting-based) be preferred?

Remember: It's crucial to fully understand the problem's constraints and requirements before attempting to solve it. By asking these clarifying questions, you'll ensure that your solution aligns with the interviewer's expectations and avoids potential misunderstandings.

Solutions

Check sum of two elements is equal to target element.

Approach – Brute Force Technique


Run two nested loops to check sum of two elements is equal to target element.

Steps

  1. Run a loop up to length of array element with nested loop.

  2. Inside, nested loop check if sum of first loop current element and current element of second loop element are equal to target then indices of both both numbers.

  3. Check till end of entire loop.

  4. If target not found then return empty array.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {


          int[] result= new int[2];

            for (int i=0; i<nums.Length; i++)
            {

                for (int j = i+1; j < nums.Length; j++)
                {
                     
                    if (nums[j]+nums[i]==target )
                    {
                        result[0] = i;
                        result[1] = j;
                        return result;
                    }
                }
            }
        
        return result;
    }
 
}

Complexity

  • Time Complexity: O(n²)

  • Auxiliary Space: O(1)

Approach – Using Hash Table


Copy array elements into a hash table and loop over array to check reminder number from hash table.

Steps

  1. Run a loop to copy all array elements and their indices into a hash table.

  2. Run a loop to check reminder number exists in hash table and index of that number is not same as current number then return indices of both both numbers.

  3. If target not found then return empty array.

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {

        int[] result = [0, 0];
        Dictionary<int, int> map = new();

        for (int i = 0; i < nums.Length; i++)
        {
            if (!map.ContainsKey(nums[i]))
            {
                map.Add(nums[i], i);
            }
        }
        for (int i = 0; i < nums.Length; i++)
        {
            int reminder = target - nums[i];
            if (map.ContainsKey(reminder) && map[reminder] != i)
            {
                result[0] = i;
                result[1] = map[reminder];
                return result;
            }

        }

        return result;
    }

}

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(n)

PreviousArrayNextTwo Sum II - Input Array Is Sorted

Last updated 1 year ago