Intuition

This problem is a classic array problem that requires us to find the position to insert a target in an array. I solve this problem by looping through the array elements and checking if the target is smaller than the current element.

Approach

1. Loop through the array elements and check if the target is smaller than or equal to the current element. If it is, return the current index.
2. If not, return the size of the array as the target position.

Complexity

• Time complexity:
  • $$O(n)$$, because in the worst case we may have to loop through all elements of the array.
• Space complexity:
  • $$O(1)$$, because we only use a constant amount of extra space.

Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(size_t i = 0; i < nums.size(); i++){
            if(target <= nums[i]) return i;
        }
        return nums.size();
    }
};