CODEWITHSUNDEEP
javaalgorithmtime-complexity
sunsin1985
sunsin1985

Reputation: 2607

What is the time complexity of my solution?

Scenario:

I have a method called "searchRange" where I need to search for the min and max index where target occurs in the supplied input array.

Question:

I think the time complexity of this solution is O(n) because I am looping over the input just once. Is my understanding correct?

Code:

public class Solution {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null) {
            return new int[2];
        }
        int min = -1, max = -1, l = nums.length;
        int[] ans = new int[2];
        for (int i = 0; i < l; i++) {
            if (nums[i] == target) {
                if (min == -1) {
                    min = i;
                } else {
                    max = Math.max(i, max);
                }
            }
        }
        if (min != -1 && max == -1) {
            max = min;
        }
        ans[0] = min;
        ans[1] = max;
        return ans;
    }
}

EDIT

Thanks, I now know that the time complexity of the above algorithm is O(n). I am trying to reach towards O(logn). I tried to use a variant of binary search to discover the min and max indices. Is the time complexity of the method given below O(logn)?

public int[] searchRange(int[] nums, int target) {
    if (nums == null)
        return new int[2];
    return searchRange(nums, target, 0, nums.length - 1);
}

public int[] searchRange(int[] nums, int target, int l, int h) {
    int[] ans = new int[] { -1, -1 };
    int middle = (l + h) / 2;
    if (l > h)
        return ans;
    if (nums[middle] == target) {
        if (middle < nums.length - 1 && nums[middle + 1] == target) {
            int[] right = searchRange(nums, target, middle + 1, h);
            ans[1] = right[1];
            ans[0] = middle;
        }
        if (middle >= 1 && nums[middle - 1] == target) {
            int[] left = searchRange(nums, target, l, middle - 1);
            ans[0] = left[0];
            if (ans[1] == -1) {
                ans[1] = middle;
            }
        }
        if (ans[0] == ans[1] && ans[0] == -1) {
            ans[0] = ans[1] = middle;
        }
    } else if (nums[middle] < target) {
        return searchRange(nums, target, middle + 1, h);
    } else {
        return searchRange(nums, target, l, middle - 1);
    }
    return ans;
}

Upvotes: 2

Views: 352

Answers (1)

argyle
argyle

Reputation: 1339

Looks like a simple O(n) where n is the length of your input array. You are going to loop through the entire array on every call to the searchRange() function.

Upvotes: 2

Related Questions