# Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

343 questions
Filter by
Sorted by
Tagged with
812 views

### Reverse a sentence in Java

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word. Implement a function ...
983 views

### Next palindromic number

I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient? ...
85 views

### For every integer in an array, find the nearest greater integer both before and after it

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of $O(n^2)$ complexity but I am not able to get anywhere near to optimizing it. ...
40 views

### Finding time complexity of my solution to the 'longest palindrome' problem in Python

Here is a short version! ...
1k views

### Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
108 views

### Compare Strings

You have been given two strings, A and B (of length N each) and Q queries. The strings contain only 0s and/or 1s. For every query, you are given an index i. You have to update the value at ...
2k views

### Program to shorten URL and decode it back to get original URL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL. Design the encode and ...
552 views

### Max Increase to Keep City Skyline in Java

In a 2-dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can ...
485 views

### Pancake sort inteview using java

Given an array of integers arr: Write a function flip(arr, k) that reverses the order of the first k elements in the array <...
175 views

### Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
60 views

### Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
510 views

### Finding the majority element in a sequence of integers in $O(n \log n)$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in $O(n \log n)$. The majority element is defined as the ...
791 views

### Merge non overlapping intervals

Merge Intervals Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their ...
578 views

### Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
1k views

### Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
199 views

### “Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
377 views

### Hackerrank “Breaking the Record” solution

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken. Easiest way for me was to ...
71 views

### Compute leaderboard of competitive riders throughout a season

I have a table in my DB that contains Riders as rows and their points throughout the season as columns. Here are the columns: ...
972 views

### Power of two integers

Challenge: Given a positive integer which fits in a $32$ bit signed integer, find if it can be expressed as $A^P$ where $P > 1$ and $A > 0$. A and P both should be integers. ...
413 views

### Return the optimal time slot

Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of ...
2k views

### Return the anti-diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: ...
205 views

### Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
40 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
995 views

### Find The Duplicates in two arrays

Find The Duplicates Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note ...
331 views

### Space complexity of the “add two binary strings” challenge

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time ...
122 views

### 2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
77 views

### Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into ...
532 views

### Detecting if two strings are anagrams

I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity ($O(n)$ where $n$ is the length ...
528 views

### Bottom-up singly linked list merge sort in C++

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach. The requirement was simply "implement a merge sort for a ...
134 views

### Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
1k views

### Sort multidimensional array based of the difference in the value

Sort multidimensional array based of the difference in the value, if value is same sort on first column. Constrains: No of rows can be any but fixed no of column ie 2. Example: <...
117 views

### Finding duplicates in arrays

I'm given two sorted arrays, arr1 and arr2. They can either be of the same length or arr2 ...
310 views

### Pig Latin Script and Runtime

Wrote a basic pig latin script in python where the input is a string and it outputs the pig latin equivalent. I was just wondering what the runtime of this code would be and if there was a way to make ...
111 views

### Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
615 views

### Genomic Range Query in Python

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task. The solution in Python is based on prefix sum, and ...
48 views

### RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
932 views

### Most popular element with count in Array with Java

Here is the input array of int values Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 } Find the most repeated element with its count, example output; ...
106 views

### Adding input strings and finding occurrences of certain prefixes

A user inputs data using a keyword add word and when he wants to find words with particular prefix then he enters find keyword. ...
241 views

### Find all pairs in an array whose absolute difference equals x

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute ...
306 views

### Design a O(1) data structure

How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a ...
414 views

### N queens variation recursion Python 3

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
61 views

### Given an array of integers, find and print its number of negative subarrays on a new line

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line. My code is taking $\mathcal{O}(n^2)$ time. How can I improve ...
1k views

### Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
498 views

### Adding Combinations of Numbers in an Array

Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops? Take an array of integers and return a list of sums of every ...
972 views

### Python PEMDAS calculator [closed]

The goal of this calculator is to evaluate an expression with PEMDAS in mind (no parenthesis yet, adding soon). Although the program works, I want to make it as efficient as possible with the approach ...
1k views

### Maximum consecutive subarray sum for a variable sliding window size

The Problem: Given an array of integers L find the largest sum of a consecutive subarray of size k or less. Constraints: ...
210 views

### Category of sorting algorithm and complexity [closed]

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm ...
2k views

### Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...