Merge Sorted Array

🎯

Merge Sorted Array

easyTWO_POINTERAmazonGoogleFacebook

Imagine you have two sorted lists of tasks from two teams, and you want to combine them into one sorted list without losing any task or creating duplicates.

💡 This problem is a classic example of merging two sorted arrays. Beginners often struggle because they try to merge from the front, which can overwrite elements and require extra space. Understanding how to merge from the back helps avoid these issues and is a foundational two-pointer technique.

📋

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums2 into nums1 as one sorted array. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

nums1.length == m + nnums2.length == n0 <= m, n <= 10^5-10^9 <= nums1[i], nums2[j] <= 10^9

💡

Example

Input"nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3"

Output[1,2,2,3,5,6]

We merge nums2 into nums1 in sorted order. Starting from the end avoids overwriting elements.

• m = 0, nums1 empty except zeros → nums1 becomes nums2
• n = 0, nums2 empty → nums1 remains unchanged
• nums1 and nums2 have all elements equal → merged array contains duplicates
• nums1 and nums2 have negative and positive numbers → merged array sorted correctly

⚠️

Common Mistakes

Merging from the front overwrites unprocessed elements in nums1

Incorrect merged array or lost elements

✅ Merge from the back using pointers starting at the end

Not copying remaining elements from nums2 after main loop

Missing elements in final merged array

✅ Add a loop to copy leftover nums2 elements after merging

Using extra space unnecessarily when in-place is possible

Higher space complexity, less optimal solution

✅ Use the backwards two-pointer approach to merge in-place

Sorting the combined array ignoring the sorted property

Slower solution with unnecessary overhead

✅ Use two-pointer merging to leverage sorted arrays

🧠

Brute Force (Copy and Sort)

💡 This approach is the most straightforward and helps beginners understand the problem by ignoring in-place constraints. It shows the simplest way to merge by combining and sorting, which is easy but inefficient.

Intuition

Combine both arrays into one big array and then sort it. This guarantees a sorted result but does not use the fact that the arrays are already sorted.

Algorithm

1. Copy the first m elements of nums1 into a temporary array.
2. Copy all elements of nums2 into the temporary array after the copied elements.
3. Sort the temporary array.
4. Copy the sorted elements back into nums1.

💡 This algorithm is easy to visualize but inefficient because it ignores the sorted property and uses extra space.

</>

Code

def merge(nums1, m, nums2, n):
    temp = nums1[:m] + nums2[:n]
    temp.sort()
    for i in range(m + n):
        nums1[i] = temp[i]

# Driver code
if __name__ == "__main__":
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    merge(nums1, m, nums2, n)
    print(nums1)

Line Notes

temp = nums1[:m] + nums2[:n]Combine the valid parts of nums1 and all of nums2 into a new list

temp.sort()Sort the combined list to get the merged sorted array

for i in range(m + n)Overwrite nums1 with the sorted elements from temp

nums1[i] = temp[i]Update nums1 in-place to meet problem requirements

import java.util.Arrays;
public class Solution {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        for (int i = 0; i < m; i++) temp[i] = nums1[i];
        for (int i = 0; i < n; i++) temp[m + i] = nums2[i];
        Arrays.sort(temp);
        for (int i = 0; i < m + n; i++) nums1[i] = temp[i];
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = {2,5,6};
        int n = 3;
        merge(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }
}

Line Notes

int[] temp = new int[m + n];Create a temporary array to hold all elements

for (int i = 0; i < m; i++) temp[i] = nums1[i];Copy valid elements from nums1

Arrays.sort(temp);Sort the combined array to merge

for (int i = 0; i < m + n; i++) nums1[i] = temp[i];Copy sorted elements back to nums1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    vector<int> temp(m + n);
    for (int i = 0; i < m; i++) temp[i] = nums1[i];
    for (int i = 0; i < n; i++) temp[m + i] = nums2[i];
    sort(temp.begin(), temp.end());
    for (int i = 0; i < m + n; i++) nums1[i] = temp[i];
}

int main() {
    vector<int> nums1 = {1,2,3,0,0,0};
    int m = 3;
    vector<int> nums2 = {2,5,6};
    int n = 3;
    merge(nums1, m, nums2, n);
    for (int x : nums1) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> temp(m + n);Temporary vector to hold all elements combined

for (int i = 0; i < m; i++) temp[i] = nums1[i];Copy first m elements from nums1

sort(temp.begin(), temp.end());Sort the combined vector to merge

for (int i = 0; i < m + n; i++) nums1[i] = temp[i];Overwrite nums1 with sorted elements

function merge(nums1, m, nums2, n) {
    let temp = nums1.slice(0, m).concat(nums2.slice(0, n));
    temp.sort((a, b) => a - b);
    for (let i = 0; i < m + n; i++) {
        nums1[i] = temp[i];
    }
}

// Driver code
let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);

Line Notes

let temp = nums1.slice(0, m).concat(nums2.slice(0, n));Create a new array combining valid nums1 and all nums2 elements

temp.sort((a, b) => a - b);Sort the combined array numerically

for (let i = 0; i < m + n; i++) {Overwrite nums1 with sorted elements

nums1[i] = temp[i];Update nums1 in-place as required

⏱

Complexity

TimeO((m+n) log(m+n))

SpaceO(m+n)

We combine both arrays into a new array of size m+n and sort it, which takes O((m+n) log(m+n)) time and O(m+n) space.

💡 For n=1000, this means about 1000*log(1000) ≈ 10,000 operations, which is inefficient compared to linear merging.

Interview Verdict: Accepted but inefficient

This approach works but is not optimal. It wastes the sorted property and extra space, so interviewers expect better.

🧠

Better Approach (Two Pointers Forward with Extra Space)

💡 This approach uses two pointers to merge the arrays in sorted order but uses extra space to avoid overwriting nums1 elements. It introduces the two-pointer technique and shows how to merge efficiently without sorting.

Intuition

Use two pointers starting at the beginning of nums1 and nums2, compare elements, and build a new sorted array. Then copy back to nums1.

Algorithm

1. Create a temporary array to hold merged elements.
2. Initialize two pointers at the start of nums1 and nums2.
3. Compare elements at pointers, append smaller to temp, and move that pointer.
4. After one array is exhausted, append remaining elements from the other.
5. Copy temp back to nums1.

💡 This algorithm is easier to implement than in-place merging and helps understand the two-pointer technique.

</>

Code

def merge(nums1, m, nums2, n):
    temp = []
    i = 0
    j = 0
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            temp.append(nums1[i])
            i += 1
        else:
            temp.append(nums2[j])
            j += 1
    while i < m:
        temp.append(nums1[i])
        i += 1
    while j < n:
        temp.append(nums2[j])
        j += 1
    for k in range(m + n):
        nums1[k] = temp[k]

# Driver code
if __name__ == "__main__":
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    merge(nums1, m, nums2, n)
    print(nums1)

Line Notes

temp = []Temporary list to store merged elements

while i < m and j < n:Loop until one array is fully traversed

if nums1[i] < nums2[j]:Pick smaller element to maintain sorted order

for k in range(m + n):Copy merged elements back to nums1

import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        ArrayList<Integer> temp = new ArrayList<>();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) temp.add(nums1[i++]);
            else temp.add(nums2[j++]);
        }
        while (i < m) temp.add(nums1[i++]);
        while (j < n) temp.add(nums2[j++]);
        for (int k = 0; k < m + n; k++) nums1[k] = temp.get(k);
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = {2,5,6};
        int n = 3;
        merge(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }
}

Line Notes

ArrayList<Integer> temp = new ArrayList<>();Temporary list to hold merged elements

while (i < m && j < n)Traverse both arrays until one is exhausted

if (nums1[i] < nums2[j]) temp.add(nums1[i++]);Add smaller element to temp

for (int k = 0; k < m + n; k++) nums1[k] = temp.get(k);Copy merged elements back to nums1

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    vector<int> temp;
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) temp.push_back(nums1[i++]);
        else temp.push_back(nums2[j++]);
    }
    while (i < m) temp.push_back(nums1[i++]);
    while (j < n) temp.push_back(nums2[j++]);
    for (int k = 0; k < m + n; k++) nums1[k] = temp[k];
}

int main() {
    vector<int> nums1 = {1,2,3,0,0,0};
    int m = 3;
    vector<int> nums2 = {2,5,6};
    int n = 3;
    merge(nums1, m, nums2, n);
    for (int x : nums1) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> temp;Temporary vector to store merged elements

while (i < m && j < n)Loop until one array is fully merged

if (nums1[i] < nums2[j]) temp.push_back(nums1[i++]);Add smaller element to temp

for (int k = 0; k < m + n; k++) nums1[k] = temp[k];Copy merged elements back to nums1

function merge(nums1, m, nums2, n) {
    let temp = [];
    let i = 0, j = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            temp.push(nums1[i++]);
        } else {
            temp.push(nums2[j++]);
        }
    }
    while (i < m) temp.push(nums1[i++]);
    while (j < n) temp.push(nums2[j++]);
    for (let k = 0; k < m + n; k++) {
        nums1[k] = temp[k];
    }
}

// Driver code
let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);

Line Notes

let temp = [];Temporary array to hold merged elements

while (i < m && j < n)Traverse both arrays until one is exhausted

if (nums1[i] < nums2[j]) {Add smaller element to temp

for (let k = 0; k < m + n; k++) {Copy merged elements back to nums1

⏱

Complexity

TimeO(m + n)

SpaceO(m + n)

We traverse both arrays once and use extra space proportional to their combined size.

💡 For n=1000, this means about 2000 operations and 2000 extra space, which is better than sorting but still uses extra memory.

Interview Verdict: Accepted, better but not optimal

This approach is a good stepping stone to the optimal in-place solution and shows understanding of two-pointer merging.

🧠

Optimal Approach (Two Pointers Backwards In-Place)

💡 This is the optimal solution that merges nums2 into nums1 in-place by using two pointers starting from the end. It avoids extra space and overwriting issues by filling nums1 from the back.

Intuition

Since nums1 has extra space at the end, start merging from the largest elements at the end to avoid overwriting unmerged elements.

Algorithm

1. Initialize three pointers: i at m-1 (end of valid nums1), j at n-1 (end of nums2), and k at m+n-1 (end of nums1).
2. Compare nums1[i] and nums2[j]. Place the larger at nums1[k].
3. Move the pointer (i or j) of the placed element and decrement k.
4. If nums2 still has elements left, copy them into nums1.
5. No need to copy remaining nums1 elements as they are already in place.

💡 This algorithm cleverly uses the extra space at the end of nums1 and merges backwards to avoid overwriting.

</>

Code

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

# Driver code
if __name__ == "__main__":
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    merge(nums1, m, nums2, n)
    print(nums1)

Line Notes

i = m - 1Pointer to last valid element in nums1

j = n - 1Pointer to last element in nums2

while i >= 0 and j >= 0:Loop until one array is fully merged

nums1[k] = nums1[i]Place larger element at the end to avoid overwriting

import java.util.Arrays;
public class Solution {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
        while (j >= 0) nums1[k--] = nums2[j--];
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = {2,5,6};
        int n = 3;
        merge(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }
}

Line Notes

int i = m - 1, j = n - 1, k = m + n - 1;Initialize pointers at the end of valid elements and total array

while (i >= 0 && j >= 0)Merge until one array is exhausted

nums1[k--] = nums1[i--];Place larger element from nums1 at the end

while (j >= 0) nums1[k--] = nums2[j--];Copy remaining nums2 elements if any

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }
    while (j >= 0) nums1[k--] = nums2[j--];
}

int main() {
    vector<int> nums1 = {1,2,3,0,0,0};
    int m = 3;
    vector<int> nums2 = {2,5,6};
    int n = 3;
    merge(nums1, m, nums2, n);
    for (int x : nums1) cout << x << " ";
    cout << endl;
    return 0;
}

Line Notes

int i = m - 1, j = n - 1, k = m + n - 1;Pointers start from the end of valid elements and total array

while (i >= 0 && j >= 0)Merge elements from the back until one array is exhausted

nums1[k--] = nums1[i--];Place larger element from nums1 at the end

while (j >= 0) nums1[k--] = nums2[j--];Copy leftover nums2 elements if any

function merge(nums1, m, nums2, n) {
    let i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

// Driver code
let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);

Line Notes

let i = m - 1, j = n - 1, k = m + n - 1;Initialize pointers at the end of valid elements and total array

while (i >= 0 && j >= 0)Merge elements from the back until one array is exhausted

nums1[k--] = nums1[i--];Place larger element from nums1 at the end

while (j >= 0) { nums1[k--] = nums2[j--]; }Copy remaining nums2 elements if any

⏱

Complexity

TimeO(m + n)

SpaceO(1)

We traverse both arrays once and merge in-place without extra space.

💡 For n=1000, this means about 2000 operations and no extra memory, which is optimal.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews as it uses the sorted property and extra space efficiently.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, you should code the optimal in-place approach after briefly explaining the brute force and better approaches.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Copy and Sort)	O((m+n) log(m+n))	O(m+n)	No	N/A	Mention only - never code
2. Better (Two Pointers Forward with Extra Space)	O(m + n)	O(m + n)	No	N/A	Explain to show understanding of two pointers
3. Optimal (Two Pointers Backwards In-Place)	O(m + n)	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to better and optimal solutions, and practice coding the optimal one. Use the common mistakes and follow-ups to prepare for curveballs.

How to Present

Clarify the problem constraints and input/output format.Explain the brute force approach to show understanding.Discuss the two-pointer technique and the better approach.Present the optimal in-place merging approach.Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of two-pointer techniques, in-place array manipulation, and ability to optimize space and time complexity.

Common Follow-ups

• What if nums1 does not have enough space? → Use extra space or return a new array.
• Can you merge if arrays are not sorted? → No, sorting or other methods needed.

💡 These follow-ups test your ability to adapt the solution to different constraints and understand the problem assumptions.

🔍

Pattern Recognition

When to Use

1) Two sorted arrays or lists, 2) Need to merge or combine, 3) Extra space available at the end of one array, 4) In-place merging desired

Signature Phrases

merge nums2 into nums1nums1 has extra space at the end

NOT This Pattern When

Sorting an unsorted array or merging unsorted arrays without extra space

Similar Problems

Merge Two Sorted Lists - similar merging concept but with linked listsIntersection of Two Arrays - uses two pointers on sorted arrays

Practice

1. Consider the following code snippet that partitions an array by parity in-place. What is the value of insertPos after the loop completes when the input is [3, 1, 2, 4]?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace insertPos updates

   Initially insertPos=0. Iteration i=0: nums[0]=3 (odd), no change. i=1: nums[1]=1 (odd), no change. i=2: nums[2]=2 (even), swap nums[2] and nums[0], insertPos=1. i=3: nums[3]=4 (even), swap nums[3] and nums[1], insertPos=2.

2. Step 2: Final value of insertPos

   After loop, insertPos=2 because two even numbers were placed at front.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two evens found, insertPos increments twice [OK]

Hint: insertPos increments once per even element [OK]

Common Mistakes:

• Counting odd elements as increments
• Off-by-one errors in insertPos after last iteration
• Confusing insertPos with current index i

2. Consider the following code snippet for removing duplicates from a sorted array allowing at most two duplicates. What is the value of write_index after processing the input [1,1,2]?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace write_index and read_index for input [1,1,2]

   Initially, write_index=0. Iteration 0: write_index<2, write 1, write_index=1. Iteration 1: write_index=1<2, write 1, write_index=2. Iteration 2: nums[2]=2 != nums[0]=1, write 2, write_index=3.

2. Step 2: Final write_index value

   After processing all elements, write_index=3, indicating the length of the modified array.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All elements allowed, write_index matches array length [OK]

Hint: write_index increments for allowed duplicates [OK]

Common Mistakes:

• Off-by-one errors in write_index
• Confusing read_index with write_index
• Not handling first two elements separately

3. What is the time complexity of the optimal 3Sum solution that sorts the array and uses a hash set for the two-sum complement search for each fixed element?

medium

A. O(n^3) because of nested loops and hash set operations

B. O(n^2) because for each element, we scan the rest with a hash set lookup in O(1)

C. O(n log n) due to sorting and linear two-pointer scans

D. O(n^2 log n) because sorting and hash set insertions dominate

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n), which is dominated by later steps.

2. Step 2: Analyze nested loops and hash set usage

   Outer loop runs n times; inner loop runs up to n times; hash set operations inside inner loop are O(1) each, but overall complexity is O(n^2).

3. Step 3: Clarify complexity of hash set approach

   The hash set approach inside the inner loop leads to O(n^2) complexity, not O(n^3).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Hash set lookups are O(1), so total is O(n^2) [OK]

Hint: Sorting O(n log n) < O(n²) nested loops dominate [OK]

Common Mistakes:

• Confusing hash set insertions as O(n)
• Thinking sorting dominates
• Assuming triple nested loops remain

4. The following code attempts to implement the optimal 4Sum solution. Which line contains a subtle bug that can cause quadruplets with repeated indices to be included, violating problem constraints?

from typing import List
from collections import defaultdict

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    two_sum_map = defaultdict(list)
    res = set()
    for i in range(n):
        for j in range(i + 1, n):
            two_sum_map[nums[i] + nums[j]].append((i, j))
    for sum1 in two_sum_map:
        sum2 = target - sum1
        if sum2 not in two_sum_map:
            continue
        list1 = two_sum_map[sum1]
        list2 = two_sum_map[sum2]
        for (i, j) in list1:
            for (k, l) in list2:
                # BUG: Missing index overlap check
                quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                res.add(quad)
    return [list(quad) for quad in sorted(res)]

medium

A. Line that combines pairs into quadruplets without checking index overlap.

B. Line that appends pairs to two_sum_map.

C. Line that sorts the input array.

D. Line that returns the final list of quadruplets.

Solution

1. Step 1: Identify where index overlap is checked

   The code must ensure indices i,j,k,l are distinct to avoid repeated elements.

2. Step 2: Locate missing check

   The nested loops combining pairs lack any condition verifying indices are unique, allowing invalid quadruplets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing index overlap check causes subtle bug [OK]

Hint: Check index overlap before adding quadruplets [OK]

Common Mistakes:

• Forgetting index uniqueness check in pair combinations

5. What is the time complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because it involves multiple swaps and pointer movements

B. O(n) but with O(n) extra space for auxiliary arrays

C. O(n^2) because swapping elements can cause repeated scanning

D. O(n) because each element is visited at most once with constant-time swaps

Solution

1. Step 1: Analyze loop iterations

   The algorithm uses three pointers and processes each element at most once, moving mid pointer forward or swapping with high pointer.

2. Step 2: Understand why complexity is O(n)

   Each swap or pointer move is O(1), and total operations are proportional to n, so time complexity is O(n). Candidates may confuse swaps causing repeated scans, but high pointer moves backward, ensuring no element is processed twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Algorithm is linear time with constant space [OK]

Hint: Each element processed once, swaps don't repeat work [OK]

Common Mistakes:

• Thinking swaps cause O(n^2)
• Confusing with quicksort complexity
• Assuming extra space needed