Why time varies from 20ms to 108ms (with C++ recursive solution)

  • 0

    My code is as followed:

    class Solution {
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            return sort(nums,0,nums.size());
        TreeNode* sort(vector<int> &nums,int start,int end){
            if(end == start) return NULL;
            int mid = (end+start)/2;
            TreeNode* root = new TreeNode(nums[mid]);
            root->left = sort(nums,start,mid);
            root->right = sort(nums,mid+1,end);
            return root;

    This code will run in 20ms.
    I just found that if I delete the "&" before nums in the variables declaration part, the time will increase to 108ms. I just cannot understand what's the reason of this.

  • 0

    Without &, nums is passed by value. So each time you call sort(...), nums will be copied. Copy is time consuming.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.